论文标题
提起的多层研究的多面体研究
A Polyhedral Study of Lifted Multicuts
论文作者
论文摘要
数据分析中许多应用的基础是图的分解，即设置为组件诱导子集的节点的分区。编码分解的一种方法是多形，这是跨越不同组件的边缘的子集。最近，在图像分析领域提出了从图$ g =（v，e）$从图$ g =（v，e）$抬起到增强图$ \ hat g =（v，e \ cup f）$，目的是获得图形分解的更具表现性的特征，对pairs $ f \ f \ f \ sebseeq \ subseeq \ selet} v pairss of the tbep} v}非邻居节点是相同的或不同的组成部分。在这项工作中，我们详细研究了$ \ mathbb {r}^{e \ cup f} $中的polytope，其顶点恰恰是$ g $的多形的特征矢量，从$ g $提起，尤其是将其连接到现有的clique protitioning protitioning and comptitioning and complique commenting and。
Fundamental to many applications in data analysis are the decompositions of a graph, i.e. partitions of the node set into component-inducing subsets. One way of encoding decompositions is by multicuts, the subsets of those edges that straddle distinct components. Recently, a lifting of multicuts from a graph $G = (V, E)$ to an augmented graph $\hat G = (V, E \cup F)$ has been proposed in the field of image analysis, with the goal of obtaining a more expressive characterization of graph decompositions in which it is made explicit also for pairs $F \subseteq \tbinom{V}{2} \setminus E$ of non-neighboring nodes whether these are in the same or distinct components. In this work, we study in detail the polytope in $\mathbb{R}^{E \cup F}$ whose vertices are precisely the characteristic vectors of multicuts of $\hat G$ lifted from $G$, connecting it, in particular, to the rich body of prior work on the clique partitioning and multilinear polytope.
