Holger S. G. Heidrich

A 4-Approximation Algorithm for Min Max Correlation Clustering

We introduce a lower bounding technique for the min max correlation clustering problem and, based on this technique, a combinatorial 4-approximation algorithm for complete graphs. This improves upon the previous best known approximation guarantees of 5, using a linear program formulation (Kalhan et…