  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.
