%0 Journal Article %1 Heidrich2023-jd %A Heidrich, Holger %A Irmai, Jannik %A Andres, Bjoern %D 2023 %I arXiv %K %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., 2023a). 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.

@article{Heidrich2023-jd, 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., 2023a). 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-09-10T10:41:24.000+0200}, author = {Heidrich, Holger and Irmai, Jannik and Andres, Bjoern}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/257246ed46d619e6cfa9be6823c8ef028/scadsfct}, interhash = {c5fbf9ab525cab2f2d62b3a7852e174c}, intrahash = {57246ed46d619e6cfa9be6823c8ef028}, keywords = {}, publisher = {arXiv}, timestamp = {2024-09-10T10:47:32.000+0200}, title = {A 4-approximation algorithm for min max correlation clustering}, year = 2023 }