%0 Conference Paper %1 7ebf7869c43a48e691ffaaa7c1de26bb %A Heidrich, Holger S. G. %A Irmai, Jannik %A Andres, Bjoern %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %D 2024 %I Cambridge MA: JMLR %K FIS_scads imported topic_visualcomputing yaff %P 1945--1953 %T A 4-Approximation Algorithm for Min Max Correlation Clustering. %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.

@inproceedings{7ebf7869c43a48e691ffaaa7c1de26bb, 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. }, added-at = {2024-11-28T16:27:18.000+0100}, author = {Heidrich, {Holger S. G.} and Irmai, Jannik and Andres, Bjoern}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/238237367212544e3aa76f784ae71d781/scadsfct}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, interhash = {fbbe6a34c89e7ac4ca8d3b08f59aac6c}, intrahash = {38237367212544e3aa76f784ae71d781}, keywords = {FIS_scads imported topic_visualcomputing yaff}, language = {English}, note = {Publisher Copyright: Copyright 2024 by the author(s).}, pages = {1945--1953}, publisher = {Cambridge MA: JMLR}, series = {Proceedings of Machine Learning Research}, timestamp = {2025-07-29T10:29:43.000+0200}, title = {A 4-Approximation Algorithm for Min Max Correlation Clustering.}, year = 2024 }