作者：Davies, Sami; Moseley, Benjamin; Newman, Heather
作者单位：University of California System; University of California Berkeley; Carnegie Mellon University; Vassar College
摘要：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 i...
