mlsanityData to 7 Oct 2026

A 4-approximation algorithm for min max correlation clustering

arXiv 2310.09196 ↗First posted 13 Oct 2023cs.DS cs.DM cs.LGcited by 4

Not on the map. Why?

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.

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

Builds on

9 of 37 references.

References · 9

  1. 2020Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Modelscited by 116
  2. 2022Correlation Clustering with Sherali-Adamscited by 15
  3. 2021Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Boundscited by 12
  4. 2015Correlation Clustering and Biclustering with Locally Bounded Errorscited by 9
  5. 2017Local Guarantees in Graph Cuts and Clusteringcited by 8
  6. 2023Fast Combinatorial Algorithms for Min Max Correlation Clusteringcited by 7
  7. 2021Correlation Clustering with Asymmetric Classification Errorscited by 6
  8. 2014Coalition Structure Generation over Graphscited by 5
  9. 2019Min-Max Correlation Clustering via MultiCutcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  2. 2024Multilayer Correlation Clusteringcited by 0
  3. 2025Online Correlation Clustering: Simultaneously Optimizing All ℓp-normscited by 0
  4. 2026Correlation Clustering with Random Partial Informationcited by 0