Google Research

Correlation Clustering with Sherali-Adams

FOCS'22 (2022) (to appear)


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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work