提出图像分割新方法，揭示多分离器多面体的完整结构。
The canonical facets of multi-separator polytopes
- 从整数规划出发，刻画多面体的全部有效不等式。
- 对路径图实现完全对偶整数描述，精度更高。
- 连接多个经典多面体，为算法设计提供理论基础。
我们首次系统研究Irmai等人（2024）提出的图多分离器问题，作为图像分割中提升多割问题的替代方案。基于整数线性规划（ILP）及其可行解生成的多分离器多面体，我们通过图论中可高效判定的条件，刻画了由该ILP不等式导出的所有极面。进一步强化这些不等式，并揭示了部分多分离器多面体的新极面。特别地，在考虑所有顶点对分离的情况下，我们获得了路径图上多分离器多面体的完全对偶整数描述。此外，我们发现奇圈不等式诱导的极面无法普遍转移至多分离器多面体；同时证明了多分离器多面体与提升多割多面体互为对方某面的投影。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。