%0 Report %1 naumann2024-cut %A Naumann, Lucas Fabian %A Irmai, Jannik %A Zhao, Shengxian %A Andres, Bjoern %D 2024 %E Salakhutdinov, Ruslan %E Kolter, Zico %E Heller, Katherine %E Weller, Adrian %E Oliver, Nuria %E Scarlett, Jonathan %E Berkenkamp, Felix %K FIS_scads imported topic_visualcomputing yaff %N 235 %T Box Facets and Cut Facets of Lifted Multicut Polytopes %U https://proceedings.mlr.press/v235/naumann24a.html %X The lifted multicut problem has diverse applications in the field of computer vision. 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.

@techreport{naumann2024-cut, abstract = {The lifted multicut problem has diverse applications in the field of computer vision. 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.}, added-at = {2024-11-28T16:27:18.000+0100}, author = {Naumann, Lucas Fabian and Irmai, Jannik and Zhao, Shengxian and Andres, Bjoern}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2b8009533ff06b3f9da3ed8c18da48267/scadsfct}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, institution = {ICML}, interhash = {7c47210791d37ff327825ddefb385b83}, intrahash = {b8009533ff06b3f9da3ed8c18da48267}, keywords = {FIS_scads imported topic_visualcomputing yaff}, language = {English}, month = {21--27 Jul}, note = {DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.}, number = 235, timestamp = {2025-07-29T10:29:43.000+0200}, title = {Box Facets and Cut Facets of Lifted Multicut Polytopes}, type = {Publication}, url = {https://proceedings.mlr.press/v235/naumann24a.html}, year = 2024 }