# Min-Max Correlation Clustering via MultiCut

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2019.

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

- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [A 4-approximation algorithm for min max correlation clustering](https://mlsanity.com/paper/2310.09196/) (2023)
- [Multilayer Correlation Clustering](https://mlsanity.com/paper/2404.16676/) (2024)

## Abstract (arXiv)

Correlation clustering is a fundamental combinatorial optimization problem arising in many contexts and applications that has been the subject of dozens of papers in the literature. In this problem we are given a general weighted graph where each edge is labeled positive or negative. The goal is to obtain a partitioning (clustering) of the vertices that minimizes disagreements - weight of negative edges trapped inside a cluster plus positive edges between different clusters. Most of the papers on this topic mainly focus on minimizing total disagreement, a global objective for this problem. In this paper, we study a cluster-wise objective function that asks to minimize the maximum number of disagreements of each cluster, which we call min-max correlation clustering. The min-max objective is a natural objective that respects the quality of every cluster. In this paper, we provide the first nontrivial approximation algorithm for this problem achieving an O(√log n·maxlog(|E^-|),log(k)) approximation for general weighted graphs, where |E^-| denotes the number of negative edges and k is the number of clusters in the optimum solution. To do so, we also obtain a corresponding result for multicut where we wish to find a multicut solution while trying to minimize the total weight of cut edges on every component. The results are then further improved to obtain (i) O(r2)-approximation for min-max correlation clustering and min-max multicut for graphs that exclude Kr,r minors (ii) a 14-approximation for the min-max correlation clustering on complete graphs.