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+\varepsilon$)-approximation algorithm based on $O(1/\varepsilon^{2})$ rounds of the Sherali-Adams hierarchy. In order to round a solution to the Sherali-Adams relaxation, we adapt the correlated rounding originally developed for CSPs [BRSII], [GSII], [RT12]. With this tool, we reach an approximation ratio of $2+\varepsilon$ 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.