Fast Combinatorial Algorithms for Simultaneously Approximating All lp-Norms in Correlation Clustering
设计了首个纯组合的常数因子算法，用于相关聚类中关于分歧向量lp范数的近似，并输出一个同时对所有lp范数都达到常数近似的聚类解，算法运行时间优于以往工作。
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].