# Solving the Correlation Cluster LP in Sublinear Time

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2025.

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

- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [HERA: Historical Evidence Routing Adapter for Physical Prediction in Latent World Models](https://mlsanity.com/paper/2608.05523/) (2026)
- [On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling](https://mlsanity.com/paper/2602.13684/) (2026)
- [Enhancing Clustering: An Explainable Approach via Filtered Patterns](https://mlsanity.com/paper/2604.12460/) (2026)
- [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)

## Abstract (arXiv)

Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizing the number of inter-cluster edges plus the number of missing intra-cluster edges. CCL+24 introduced the cluster LP for Correlation Clustering, which they argued captures the problem much more succinctly than previous linear programming formulations. However, the cluster LP has exponential size, with a variable for every possible set of vertices in the input graph. Nevertheless, CCL+24 showed how to find a feasible solution for the cluster LP in time O(npoly(1/ε)) with objective value at most (1+ε) times the value of an optimal solution for the respective Correlation Clustering instance. Furthermore, they showed how to round a solution to the cluster LP, yielding a (1.485+ε)-approximation algorithm for the Correlation Clustering problem. The main technical result of this paper is a new approach to find a feasible solution for the cluster LP with objective value at most (1+ε) of the optimum in time widetilde O(2poly(1/ε) n), where n is the number of vertices in the graph. We also show how to implement the rounding within the same time bounds, thus achieving a fast (1.485+ε)-approximation algorithm for the Correlation Clustering problem. This bridges the gap between state-of-the-art methods for approximating Correlation Clustering and the recent focus on fast algorithms.