Theory Seminar

Recent progresses on Correlation Clustering

Euiwoong LeeUniversity of Michigan
3725 Beyster BuildingMap
Correlation Clustering is one of the most well-studied graph clustering problems. The input is a complete graph where each edge is labeled either “+” or “-“, and the goal is to partition the vertex set into (an arbitrary number of) clusters to minimize (the number of + edges between different clusters) + (the number of – edges within the same cluster). Until recently, the best polynomial-time approximation ratio was 2.06, nearly matching the integrality gap of 2 for the standard LP relaxation.

Since 2022, we have bypassed this barrier and progressively improved the approximation ratio, with the current ratio being 1.44. Based on a new relaxation inspired by the Sherali-Adams hierarchy, the algorithm introduces and combines several tools considered in different contexts, including “local to global correlation rounding” and “combinatorial preclusering”. In this talk, I will describe the current algorithm as well as how it has been inspired by various viewpoints.

Joint work with Nairen Cao, Vincent Cohen-Addad, Shi Li, Alantha Newman, and Lukas Vogl


Greg Bodwin


Euiwoong Lee