Analysis and Optimization of Graph Decompositions by Lifted Multicuts
Authors: Andrea Horňáková, Jan-Hendrik Lange, Bjoern Andres
ICML 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To find optimal decompositions defined by minimum cost lifted multicuts, we establish some properties of some facets of lifted multicut polytopes, define efficient separation procedures and apply these in a branchand-cut algorithm. ... The advantage of β over α can be seen in Fig. 7 for an instance of the min cost lifted multicut problem by Keuper et al. (2015) with |V | = 126, |E| = 229 and |E | = 1860. |
| Researcher Affiliation | Academia | 1Max Planck Institute for Informatics, Saarbr ucken, Germany. |
| Pseudocode | No | The paper describes algorithms in textual form (e.g., Section 6.3) but does not include any explicitly labeled pseudocode blocks or algorithm listings. |
| Open Source Code | Yes | Our code is available at https://github.com/bjoern-andres/graph. |
| Open Datasets | Yes | Depicted are two decompositions of the pixel grid graph of an image, all from (Arbel aez et al., 2011). |
| Dataset Splits | No | The paper uses a specific problem instance for evaluation but does not describe training, validation, and test splits typically found in machine learning contexts. It focuses on solving an optimization problem instance. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., CPU, GPU models, memory) used to run the experiments. |
| Software Dependencies | No | We implement these for the branch-and-cut algorithm in the software Gurobi. ... The software Gurobi is mentioned, but no version number is provided. |
| Experiment Setup | Yes | The procedure α is canonical and serves as a reference. It separates infeasible points by any of the inequalities (4) (6). Violated inequalities of (4) and (5) are found by searching for shortest chordless paths. Violated inequalities of (5) are found by searching for minimum vw-cuts. The procedure β is less canonical: It separates infeasible points by some cycle inequalities w.r.t. G (cf. Theorem 10) and by cut inequalities (6). ... The advantage of β over α can be seen in Fig. 7 for an instance of the min cost lifted multicut problem by Keuper et al. (2015) with |V | = 126, |E| = 229 and |E | = 1860. |