Skip to yearly menu bar Skip to main content


Poster

A 4-Approximation Algorithm for Min Max Correlation Clustering

Holger Heidrich · Jannik Irmai · Bjoern Andres

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

Abstract:

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.

Chat is not available.