Box Facets and Cut Facets of Lifted Multicut Polytopes
Authors: Lucas Fabian Naumann, Jannik Irmai, Shengxian Zhao, Bjoern Andres
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Exact algorithms based on linear programming require an understanding of lifted multicut polytopes. Despite recent progress, two fundamental questions about these polytopes have remained open: Which lower box inequalities define facets, and which cut inequalities define facets? In this article, we answer the first question by establishing conditions that are necessary, sufficient and efficiently decidable. Toward the second question, we show that deciding facet-definingness of cut inequalities is NP-hard. This completes the analysis of canonical facets of lifted multicut polytopes. |
| Researcher Affiliation | Academia | 1Faculty of Computer Science, TU Dresden 2Center for Scalable Data Analytics and AI, Dresden/Leipzig. |
| Pseudocode | No | The paper focuses on theoretical proofs and does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements about open-source code availability or links to repositories. |
| Open Datasets | No | This is a theoretical paper and does not involve experimental datasets or training. |
| Dataset Splits | No | This is a theoretical paper and does not involve dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not involve hardware specifications for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not mention software dependencies with version numbers for experimental setup. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or system-level training settings. |