We introduce fast algorithms for correlation clustering with respect to the Min Max objective that provide constant factor approximations on complete graphs. Our algorithms are the first purely combinatorial approximation algorithms for this problem. We construct a novel semi-metric 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 paper demonstrates empirically that, compared to prior work, our algorithms sacrifice little in the objective quality to obtain significantly better run-time. Moreover, our algorithms scale to larger networks that are effectively intractable for known algorithms.

翻译：我们引入了与Min Max目标相关的相关组合的快速算法,该算法为完整的图表提供了恒定系数近似值。我们的算法是第一个针对这一问题的纯组合近似算法。我们在一组脊椎上构建了一个新的半计量法,我们称之为相关度度,这向我们的组合算法表明对结点是否应该在同一组内。文件从经验上证明,与以往的工作相比,我们的算法在客观质量上没有牺牲多少,以获得更好的运行时间。此外,我们的算法规模到对已知算法有效难以控制的更大网络。