A 4-approximation algorithm for min max correlation clustering

Holger Heidrich, Jannik Irmai, Bjoern Andres
10/13/2023
cs.DScs.DMcs.LG

Official code: JannikIrmai/min-max-correlation-clustering (1 star, last commit 2024-05-23).

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.

View on arXivView PDF

Code Implementations(1)

JannikIrmai/min-max-correlation-clusteringOfficial
10C++, CMakeOct 13, 20232 years ago

Similar Papers

Multilayer Correlation Clustering

83% match2024

Partial Optimality in Cubic Correlation Clustering

83% match2023

Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds

82% match2023

Learning-Augmented Streaming Algorithms for Correlation Clustering

82% match2025

Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach

82% match1 repo22023

Query-Efficient Correlation Clustering with Noisy Oracle

81% match2024

Cite this paper

@article{heidrich2023approximation,
  title  = {A 4-approximation algorithm for min max correlation clustering},
  author = {Holger Heidrich and Jannik Irmai and Bjoern Andres},
  year   = {2023},
  eprint = {2310.09196},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2310.09196v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2310.09196.svg)](https://codeofpaper.com/paper/2310.09196)

Discussion