# Understanding the Cluster LP for Correlation Clustering

arXiv: https://arxiv.org/abs/2404.17509 · HTML: https://mlsanity.com/paper/2404.17509/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2024.

## Built on by (most cited first, 6 of 6)

- [Dynamic Correlation Clustering in Sublinear Update Time](https://mlsanity.com/paper/2406.09137/) (2024)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time](https://mlsanity.com/paper/2411.09979/) (2024)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)
- [A Generic Framework for Fair Consensus Clustering in Streams](https://mlsanity.com/paper/2602.11500/) (2026)
- [Correlation Clustering with Random Partial Information](https://mlsanity.com/paper/2608.16315/) (2026)

## Abstract (arXiv)

In the classic Correlation Clustering problem introduced by Bansal, Blum, and Chawla (FOCS 2002), the input is a complete graph where edges are labeled either + or -, and the goal is to find a partition of the vertices that minimizes the sum of the +edges across parts plus the sum of the -edges within parts. In recent years, Chawla, Makarychev, Schramm and Yaroslavtsev (STOC 2015) gave a 2.06-approximation by providing a near-optimal rounding of the standard LP, and Cohen-Addad, Lee, Li, and Newman (FOCS 2022, 2023) finally bypassed the integrality gap of 2 for this LP giving a 1.73-approximation for the problem. In order to create a simple and unified framework for Correlation Clustering similar to those for typical approximate optimization tasks, we propose the cluster LP as a strong linear program for Correlation Clustering. We demonstrate the power of the cluster LP by presenting new rounding algorithms, and providing two analyses, one analytically proving a 1.56-approximation and the other solving a factor-revealing SDP to show a 1.485-approximation. Both proofs introduce principled methods by which to analyze the performance of the algorithm, resulting in a significantly improved approximation guarantee. Finally, we prove an integrality gap of 4/3 for the cluster LP, showing our 1.485-upper bound cannot be drastically improved. Our gap instance directly inspires an improved NP-hardness of approximation with a ratio 24/23 ≈ 1.042; no explicit hardness ratio was known before.