# Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2014.

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

- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Differentially Private Correlation Clustering](https://mlsanity.com/paper/2102.08885/) (2021)
- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05696/) (2021)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [A Polyhedral Study of Lifted Multicuts](https://mlsanity.com/paper/2202.08068/) (2022)
- [Better Private Algorithms for Correlation Clustering](https://mlsanity.com/paper/2202.10747/) (2022)
- [Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds](https://mlsanity.com/paper/2307.06723/) (2023)
- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models](https://mlsanity.com/paper/2108.04729/) (2021)
- [Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling](https://mlsanity.com/paper/2306.04884/) (2023)
- [Dynamic Correlation Clustering in Sublinear Update Time](https://mlsanity.com/paper/2406.09137/) (2024)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals](https://mlsanity.com/paper/2601.16091/) (2026)
- [Online Correlation Clustering for Dynamic Complete Signed Graphs](https://mlsanity.com/paper/2211.07000/) (2022)
- [Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network](https://mlsanity.com/paper/2502.14536/) (2025)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Four Algorithms for Correlation Clustering: A Survey](https://mlsanity.com/paper/2208.12636/) (2022)
- [Fair Correlation Clustering in Forests](https://mlsanity.com/paper/2302.11295/) (2023)
- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)
- [Multilayer Correlation Clustering](https://mlsanity.com/paper/2404.16676/) (2024)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)
- [Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clustering](https://mlsanity.com/paper/2604.15738/) (2026)
- [Correlation Clustering with Random Partial Information](https://mlsanity.com/paper/2608.16315/) (2026)

## Abstract (arXiv)

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps: - For complete graphs our appoximation is 2.06 - varepsilon for a fixed constant varepsilon, which almost matches the previously known integrality gap of 2. - For complete k-partite graphs our approximation is 3. We also show a matching integrality gap. - For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is 1.5, and we show an integrality gap of 1.2. Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of 2.5 for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a 2-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a 4-approximation (SICOMP'12).