Metraipolis › archive › dc_d99cff456eeb

The canonical facets of multi-separator polytopes — arXiv:2608.16861

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.16861
License (as archived)
CC0-1.0
Archived
2026-10-18T19:44:35.967Z
SHA-256 of the archived text
0f77385bf4f3404ac86437f7fa19ff59668a6e1a6f92e729cc704fa54d60ab59
Stable URL of this page
https://metraipolis.com/documento/dc_d99cff456eeb

How to cite

The canonical facets of multi-separator polytopes — arXiv:2608.16861 — arXiv (en), https://arxiv.org/abs/2608.16861 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d99cff456eeb (Metraipolis archive dc_d99cff456eeb, sha256 0f77385bf4f3404ac86437f7fa19ff59668a6e1a6f92e729cc704fa54d60ab59)
BibTeX
@misc{dcd99cff456eeb,
  title = {The canonical facets of multi-separator polytopes — arXiv:2608.16861},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.16861},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d99cff456eeb; sha256 0f77385bf4f3404ac86437f7fa19ff59668a6e1a6f92e729cc704fa54d60ab59},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.16861. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 inequalities. Specifically, we obtain a totally dual integral description of the multi-separator polytope for paths in the case where separation is considered for all vertex pairs. Finally, we relate the multi-separator polytope to the boolean quadric polytope, showing that facets induced by odd-cycle inequalities do not transfer generally, and to the lifted multicut polytope, showing that either polytope is a projection of a face of the other.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-18 in cs.LG).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Machine Learning (cs.LG); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.16861 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T19:02:44.326Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).