Skip to yearly menu bar Skip to main content


A 4-Approximation Algorithm for Min Max Correlation Clustering

Holger Heidrich · Jannik Irmai · Bjoern Andres

MR1 & MR2 - Number 177
[ ]
Fri 3 May 8 a.m. PDT — 8:30 a.m. PDT


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 al., 2019), and 40, for a combinatorial algorithm (Davies et al., 2023). We extend this algorithm by a greedy joining heuristic and show empirically that it improves the state of the art in solution quality and runtime on several benchmark datasets.

Live content is unavailable. Log in and register to view live content