The canonical facets of multi-separator polytopes
We initiate a polyhedral study of the graph multi-separator problem proposed by Irmai et al. (2024) as an alternative to the lifted multicut problem for application to the task of image segmentation. Starting with an integer linear program (ILP) formulation and the multi-separator polytope spanned by its feasible solutions, we characterize in terms of efficiently-decidable, graph-theoretic conditions all facets induced by inequalities of the ILP. We proceed by strengthening these inequalities and describing additional facets of some multi-separator polytopes induced by the stronger inequalitie
Lineage graph
Paper → model → repo connections mined from source citations (Tier-1 exact match).
Why these links exist
Every edge carries a method, confidence, and the source snippet that justified it — so bad links are debuggable.
- LinkedLinked via arxiv author · 85%Bjoern Andres →
“The canonical facets of multi-separator polytopes”
- LinkedLinked via arxiv author · 85%Silvia Di Gregorio →
“The canonical facets of multi-separator polytopes”
- LinkedLinked via arxiv author · 85%Jannik Irmai →
“The canonical facets of multi-separator polytopes”
- LinkedLinked via arxiv author · 85%Lucas Fabian Naumann →
“The canonical facets of multi-separator polytopes”
- LinkedLinked via arxiv author · 85%Shengxian Zhao →
“The canonical facets of multi-separator polytopes”