Fast Combinatorial Algorithms for Simultaneously Approximating All lp-Norms in Correlation Clustering
成果类型：
Article; Early Access
署名作者：
Davies, Sami; Moseley, Benjamin; Newman, Heather
署名单位：
University of California System; University of California Berkeley; Carnegie Mellon University; Vassar College
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2024.0567
发表日期：
2025
关键词：
摘要：
We design the first purely combinatorial O(1)-factor algorithms for correlation clustering with respect to the fp-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 fp-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'''), for O(n''') the running time for matrix multiplication on n x n matrices. Further, the runtime improves to O(n triangle 2 log n), when the maximum positive degree in the graph is at most triangle.