Fast Combinatorial Algorithms for Simultaneously Approximating All ℓ_p-Norms in Correlation Clustering

We design the first purely combinatorial $O(1)$-factor algorithms for correlation clustering with respect to the ${\mathcal{\ell }}_p$-norm of the disagreement vector. Our main technical contribution is the construction of a novel semimetric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The power of the correlation metric allows us to design an algorithm that outputs a single clustering solution that is simultaneously $O(1)$-approximate for all ${\mathcal{\ell }}_p$-norms, thus proving that minimal sacrifice is needed in order to optimize different norms. Our algorithms are also faster than those in all previous works, with runtime $O(n^{\omega })$, for $O(n^{\omega })$ the running time for matrix multiplication on $n\times n$ matrices. Further, the runtime improves to $O(n{\mathrm{\Delta }}^2\log n)$, when the maximum positive degree in the graph is at most $\mathrm{\Delta }$.

Funding: B. Moseley and H. Newman were supported in part by a Google Research Award, an Infor Research Award, a Carnegie Bosch Junior Faculty Chair, NSF Division of Computing and Communication Foundations [Grants CCF-2121744 and CCF-1845146], and the Office of Naval Research Global [Grant N000142212702].