A 4-Approximation Algorithm for Min Max Correlation Clustering
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.
Cite
Text
Heidrich et al. "A 4-Approximation Algorithm for Min Max Correlation Clustering." Artificial Intelligence and Statistics, 2024.Markdown
[Heidrich et al. "A 4-Approximation Algorithm for Min Max Correlation Clustering." Artificial Intelligence and Statistics, 2024.](https://mlanthology.org/aistats/2024/heidrich2024aistats-4approximation/)BibTeX
@inproceedings{heidrich2024aistats-4approximation,
title = {{A 4-Approximation Algorithm for Min Max Correlation Clustering}},
author = {Heidrich, Holger S. G. and Irmai, Jannik and Andres, Bjoern},
booktitle = {Artificial Intelligence and Statistics},
year = {2024},
pages = {1945-1953},
volume = {238},
url = {https://mlanthology.org/aistats/2024/heidrich2024aistats-4approximation/}
}