mlsanityData to 14 Oct 2026

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

arXiv 1412.0681 ↗First posted 1 Dec 2014cs.DScited by 27

Not on the map. Why?

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

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 5; 2023: 4; 2024: 5; 2025: 4; 2026: 3.

27 papers.

Sort:

  1. 2021Correlation Clustering in Constant Many Parallel Roundscited by 15
  2. 2021Differentially Private Correlation Clusteringcited by 13
  3. 2021Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Boundscited by 12
  4. 2023Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!cited by 8
  5. 2021Local Correlation Clustering with Asymmetric Classification Errorscited by 7
  6. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  7. 2021Correlation Clustering with Asymmetric Classification Errorscited by 6
  8. 2022Near-Optimal Correlation Clustering with Privacycited by 6
  9. 2022A Polyhedral Study of Lifted Multicutscited by 3
  10. 2022Better Private Algorithms for Correlation Clusteringcited by 3
  11. 2023Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Roundscited by 3
  12. 2024Clustering with Non-adaptive Subset Queriescited by 3
15 more
  1. 2021Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Modelscited by 2
  2. 2023Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labelingcited by 2
  3. 2024Dynamic Correlation Clustering in Sublinear Update Timecited by 2
  4. 2025Learning Partitions with Optimal Query and Round Complexitiescited by 2
  5. 2026Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivalscited by 2
  6. 2022Online Correlation Clustering for Dynamic Complete Signed Graphscited by 1
  7. 2025Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social networkcited by 1
  8. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  9. 2022Four Algorithms for Correlation Clustering: A Surveycited by 0
  10. 2023Fair Correlation Clustering in Forestscited by 0
  11. 2024Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Bettercited by 0
  12. 2024Multilayer Correlation Clusteringcited by 0
  13. 2025Online Correlation Clustering: Simultaneously Optimizing All ℓp-normscited by 0
  14. 2026Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clusteringcited by 0
  15. 2026Correlation Clustering with Random Partial Informationcited by 0