TY - GEN
T1 - Solving the Correlation Cluster LP in Sublinear Time
AU - Cao, Nairen
AU - Cohen-Addad, Vincent
AU - Lee, Euiwoong
AU - Li, Shi
AU - Lolck, David Rasmussen
AU - Newman, Alantha
AU - Thorup, Mikkel
AU - Vogl, Lukas
AU - Yan, Shuyi
AU - Zhang, Hanwen
N1 - Publisher Copyright:
© 2025 Owner/Author.
PY - 2025/6/15
Y1 - 2025/6/15
N2 - 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. 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.
AB - 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. 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.
KW - Approximation Algorithms
KW - Clustering
KW - Exponential-Size Linear Programming
KW - MPC Algorithm
KW - Sublinear-Time Algorithm
UR - https://www.scopus.com/pages/publications/105009868461
U2 - 10.1145/3717823.3718181
DO - 10.1145/3717823.3718181
M3 - Conference contribution
AN - SCOPUS:105009868461
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1154
EP - 1165
BT - STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing
A2 - Koucky, Michal
A2 - Bansal, Nikhil
PB - Association for Computing Machinery
T2 - 57th Annual ACM Symposium on Theory of Computing, STOC 2025
Y2 - 23 June 2025 through 27 June 2025
ER -