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