Correlation Clustering with Sherali-Adams
Abstract
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 be-
tween 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 Correla-
tion Clustering has been actively investigated [BBC04, CGW05, ACN08], culminating in a
2.06-approximation algorithm by Chawla, Makarychev, Schramm, and Yaroslavtsev [CMSY15].
The state-of-the-art result of Chawla, Makarychev, Schramm, and Yaroslavtsev is obtained by
designing a clever rounding scheme for the standard LP relaxation. Yet, the integrality gap of
this formulation is 2 and so it has remained a major open question to determine whether one
can even breach this bound of 2 for Correlation Clustering.
In this paper, we answer the question affirmatively by showing that there exists a (1.95 +ε)-
approximation algorithm based on O(1/ε^2) rounds of the Sherali-Adams hierarchy. In order to
round a solution to Sherali-Adams, we adapt the correlated rounding originally developed for
CSPs [BRS11, GS11, RT12]. Beyond the traditional triangle-based analysis, we also employ a
global charging scheme that amortizes the total cost of the rounding across different triangles.
We believe our results
could pave the way for applications of LP hierarchies beyond CSPs.
Clustering problem asks to partition V into clusters to minimize the number of +edges be-
tween 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 Correla-
tion Clustering has been actively investigated [BBC04, CGW05, ACN08], culminating in a
2.06-approximation algorithm by Chawla, Makarychev, Schramm, and Yaroslavtsev [CMSY15].
The state-of-the-art result of Chawla, Makarychev, Schramm, and Yaroslavtsev is obtained by
designing a clever rounding scheme for the standard LP relaxation. Yet, the integrality gap of
this formulation is 2 and so it has remained a major open question to determine whether one
can even breach this bound of 2 for Correlation Clustering.
In this paper, we answer the question affirmatively by showing that there exists a (1.95 +ε)-
approximation algorithm based on O(1/ε^2) rounds of the Sherali-Adams hierarchy. In order to
round a solution to Sherali-Adams, we adapt the correlated rounding originally developed for
CSPs [BRS11, GS11, RT12]. Beyond the traditional triangle-based analysis, we also employ a
global charging scheme that amortizes the total cost of the rounding across different triangles.
We believe our results
could pave the way for applications of LP hierarchies beyond CSPs.
Research Areas
