# A 4-approximation algorithm for min max correlation clustering

arXiv: https://arxiv.org/abs/2310.09196 · HTML: https://mlsanity.com/paper/2310.09196/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 37 references that are in the map.
- First posted on arXiv 13 Oct 2023.

## Builds on (most cited first, 9 of 9)

- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [Local Guarantees in Graph Cuts and Clustering](https://mlsanity.com/paper/1704.00355/) (2017)
- [Fast Combinatorial Algorithms for Min Max Correlation Clustering](https://mlsanity.com/paper/2301.13079/) (2023)
- [Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05696/) (2021)
- [Coalition Structure Generation over Graphs](https://mlsanity.com/paper/1401.6428/) (2014)
- [Min-Max Correlation Clustering via MultiCut](https://mlsanity.com/paper/1907.00117/) (2019)

## Built on by (most cited first, 4 of 4)

- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Multilayer Correlation Clustering](https://mlsanity.com/paper/2404.16676/) (2024)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)
- [Correlation Clustering with Random Partial Information](https://mlsanity.com/paper/2608.16315/) (2026)

## Abstract (arXiv)

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.