AISTATS 2024poster8 citations
A 4-Approximation Algorithm for Min Max Correlation Clustering
Holger S. G. Heidrich, Jannik Irmai, Bjoern Andres
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.
BibTeX
@InProceedings{pmlr-v238-heidrich24a,
title = {A 4-Approximation Algorithm for Min Max Correlation Clustering},
author = {Heidrich, Holger S. G. and Irmai, Jannik and Andres, Bjoern},
booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics},
pages = {1945--1953},
year = {2024},
editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen},
volume = {238},
series = {Proceedings of Machine Learning Research},
month = {02--04 May},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v238/heidrich24a/heidrich24a.pdf},
url = {https://proceedings.mlr.press/v238/heidrich24a.html},
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.}
}