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

• Algorithms and Theory