# Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 44 references that are in the map.
- First posted on arXiv 13 Jul 2023.

## Builds on (most cited first, 17 of 17)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [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)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [Local Guarantees in Graph Cuts and Clustering](https://mlsanity.com/paper/1704.00355/) (2017)
- [Correlation Clustering in Data Streams](https://mlsanity.com/paper/1812.02023/) (2018)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [Popular conjectures imply strong lower bounds for dynamic problems](https://mlsanity.com/paper/1402.0054/) (2014)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Almost 3-Approximate Correlation Clustering in Constant Rounds](https://mlsanity.com/paper/2205.03710/) (2022)
- [Massively Parallel Correlation Clustering in Bounded Arboricity Graphs](https://mlsanity.com/paper/2102.11660/) (2021)
- [Tight Analysis of Randomized Greedy MIS](https://mlsanity.com/paper/1707.05124/) (2017)
- [Better Private Algorithms for Correlation Clustering](https://mlsanity.com/paper/2202.10747/) (2022)

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

- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)
- [Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time](https://mlsanity.com/paper/2411.09979/) (2024)

## Abstract (arXiv)

In this paper, we study parallel algorithms for the correlation clustering problem, where every pair of two different entities is labeled with similar or dissimilar. The goal is to partition the entities into clusters to minimize the number of disagreements with the labels. Currently, all efficient parallel algorithms have an approximation ratio of at least 3. In comparison with the 1.994+ε ratio achieved by polynomial-time sequential algorithms [CLN22], a significant gap exists. We propose the first poly-logarithmic depth parallel algorithm that achieves a better approximation ratio than 3. Specifically, our algorithm computes a (2.4+ε)-approximate solution and uses tildeO(m1.5) work. Additionally, it can be translated into a tildeO(m1.5)-time sequential algorithm and a poly-logarithmic rounds sublinear-memory MPC algorithm with tildeO(m1.5) total memory. Our approach is inspired by Awerbuch, Khandekar, and Rao's [AKR12] length-constrained multi-commodity flow algorithm, where we develop an efficient parallel algorithm to solve a truncated correlation clustering linear program of Charikar, Guruswami, and Wirth [CGW05]. Then we show the solution of the truncated linear program can be rounded with a factor of at most 2.4 loss by using the framework of [CMSY15]. Such a rounding framework can then be implemented using parallel pivot-based approaches.