Fast Combinatorial Algorithms for Simultaneously Approximating All ℓ_<i>p</i>-Norms in Correlation Clustering

We design the first purely combinatorial [Formula: see text]-factor algorithms for correlation clustering with respect to the [Formula: see text]-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 [Formula: see text]-approximate for all [Formula: see text]-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 [Formula: see text], for [Formula: see text] the running time for matrix multiplication on [Formula: see text] matrices. Further, the runtime improves to [Formula: see text], when the maximum positive degree in the graph is at most [Formula: see text]. 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].