A 4-approximation algorithm for min max correlation clustering
This provides an improved approximation algorithm for correlation clustering, a fundamental problem in machine learning and data analysis, though it appears incremental relative to prior work.
The authors tackled the min max correlation clustering problem by developing a combinatorial 4-approximation algorithm for complete graphs, improving upon previous guarantees of 5 and 40. They extended this with a greedy heuristic that empirically enhanced solution quality and runtime on benchmark datasets.
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.