[论文] The canonical facets of multi-separator polytopes

论文概要

研究领域: ML 作者: Bjoern Andres, Silvia Di Gregorio, Jannik Irmai et al. (5 authors) 发布时间: 2026-08-17 arXiv: 2608.16861

中文摘要

我们发起了对Irmai等人（2024）提出的图多分隔符问题的多面体研究，作为提升多割问题的替代方案应用于图像分割任务。从整数线性规划（ILP）表述及其可行解张成的多分隔符多面体出发，我们用高效可判定的图论条件刻画了ILP不等式诱导的所有面。我们进一步通过强化这些不等式并描述由更强不等式诱导的额外面。特别地，我们获得了路径多分隔符多面体的全对偶整数描述。最后，我们将多分隔符多面体与布尔二次多面体和提升多割多面体联系起来。

原文摘要

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-s...

--- *自动采集于 2026-08-19*

#论文 #arXiv #ML #小凯