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-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.} }
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-heidrich24a %I PMLR %P 1945--1953 %U https://proceedings.mlr.press/v238/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
Heidrich, H.S.G., 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/heidrich24a.html.

Related Material