Cao, NairenCohen-Addad, VincentLee, EuiwoongLi, ShiLolck, David RasmussenNewman, AlanthaThorup, MikkelVogl, LukasYan, ShuyiZhang, Hanwen2025-06-172025-06-172025-06-162025-06-1510.1145/3717823.3718181https://infoscience.epfl.ch/handle/20.500.14299/251417Correlation 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. Cao, Cohen-Addad, Lee, Li, Newman, and Vogl [STOC 2024] 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, they 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.437+ε)-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 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.437+ε)-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.en• Theory of computation → Facility location and clusteringStreaming, sublinear and near linear time algorithmsMassively parallel algorithms Clustering, Approximation Algorithms, Exponential-Size Linear Programming, Sublinear-Time Algorithm, MPC Algorithmtext::conference output::conference proceedings::conference paper