A 4-Approximation Algorithm for Min Max Correlation Clustering

Holger S.G. Heidrich, Jannik Irmai, Bjoern Andres
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:1945-1953, 2024.

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 this Paper

BibTeX
@InProceedings{pmlr-v238-s-g-heidrich24a, title = { A 4-Approximation Algorithm for Min Max Correlation Clustering }, author = {S.G. Heidrich, Holger 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/s-g-heidrich24a/s-g-heidrich24a.pdf}, url = {https://proceedings.mlr.press/v238/s-g-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. } }
Endnote
%0 Conference Paper %T A 4-Approximation Algorithm for Min Max Correlation Clustering %A Holger S.G. Heidrich %A Jannik Irmai %A Bjoern Andres %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-s-g-heidrich24a %I PMLR %P 1945--1953 %U https://proceedings.mlr.press/v238/s-g-heidrich24a.html %V 238 %X 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.
APA
S.G. Heidrich, H., Irmai, J. & Andres, B.. (2024). A 4-Approximation Algorithm for Min Max Correlation Clustering . Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:1945-1953 Available from https://proceedings.mlr.press/v238/s-g-heidrich24a.html.

Related Material