# Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2023.

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

- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [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)
- [Multilayer Correlation Clustering](https://mlsanity.com/paper/2404.16676/) (2024)
- [Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time](https://mlsanity.com/paper/2411.09979/) (2024)
- [On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling](https://mlsanity.com/paper/2602.13684/) (2026)

## Abstract (arXiv)

We consider the classic Correlation Clustering problem: Given a complete graph where edges are labelled either + or -, the goal is to find a partition of the vertices that minimizes the number of the pedges across parts plus the number of the medges within parts. Recently, Cohen-Addad, Lee and Newman [CLN22] presented a 1.994-approximation algorithm for the problem using the Sherali-Adams hierarchy, hence breaking through the integrality gap of 2 for the classic linear program and improving upon the 2.06-approximation of Chawla, Makarychev, Schramm and Yaroslavtsev [CMSY15]. We significantly improve the state-of-the-art by providing a 1.73-approximation for the problem. Our approach introduces a preclustering of Correlation Clustering instances that allows us to essentially ignore the error arising from the em correlated rounding used by [CLN22]. This additional power simplifies the previous algorithm and analysis. More importantly, it enables a new em set-based rounding that complements the previous roundings. A combination of these two rounding algorithms yields the improved bound.