论文标题
与Sherali-Adams的相关聚类
Correlation Clustering with Sherali-Adams
论文作者
论文摘要
Given a complete graph $G = (V, E)$ where each edge is labeled $+$ or $-$, the Correlation Clustering problem asks to partition $V$ into clusters to minimize the number of $+$edges between different clusters plus the number of $-$edges within the same cluster.在实践中，相关聚类已被用于对大量聚类问题进行建模，这使其成为研究最广泛的聚类公式之一。相关聚类的近似性已积极研究[BBC04，CGW05，ACN08]，最终以$ 2.06 $ - APPROXIMATION算法[CMSY15]，基于标准LP释放。由于该公式的完整性差距为2，因此仍然是一个主要的开放问题，可以确定是否可以达到2的近似因素，甚至可能被违反。 在本文中，我们通过证明存在$（1.994 +ε）$ - 基于Sherali-Adams层次结构的$ O（1/ε^2 $）回合的近似算法来回答这个问题。为了将解决方案绕到Sherali-Adams松弛，我们适应了最初为CSPS开发的{\ em相关的圆形} [BRS11，GS11，RT12]。使用此工具，我们达到相关聚类的近似值为$ 2+ε$。为了违反此比率，我们通过采用全球充电计划来超越传统的基于三角形的分析，该计划摊销了各种三角形的舍入的总成本。
Given a complete graph $G = (V, E)$ where each edge is labeled $+$ or $-$, the Correlation Clustering problem asks to partition $V$ into clusters to minimize the number of $+$edges between different clusters plus the number of $-$edges within the same cluster. Correlation Clustering has been used to model a large number of clustering problems in practice, making it one of the most widely studied clustering formulations. The approximability of Correlation Clustering has been actively investigated [BBC04, CGW05, ACN08], culminating in a $2.06$-approximation algorithm [CMSY15], based on rounding the standard LP relaxation. Since the integrality gap for this formulation is 2, it has remained a major open question to determine if the approximation factor of 2 can be reached, or even breached. In this paper, we answer this question affirmatively by showing that there exists a $(1.994 + ε)$-approximation algorithm based on $O(1/ε^2$) rounds of the Sherali-Adams hierarchy. In order to round a solution to the Sherali-Adams relaxation, we adapt the {\em correlated rounding} originally developed for CSPs [BRS11, GS11, RT12]. With this tool, we reach an approximation ratio of $2+ε$ for Correlation Clustering. To breach this ratio, we go beyond the traditional triangle-based analysis by employing a global charging scheme that amortizes the total cost of the rounding across different triangles.
