# Four Algorithms for Correlation Clustering: A Survey

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 29 references that are in the map.
- First posted on arXiv 24 Aug 2022.

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

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Multi-Person Tracking by Multicut and Deep Matching](https://mlsanity.com/paper/1608.05404/) (2016)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [Correlation Clustering in Data Streams](https://mlsanity.com/paper/1812.02023/) (2018)
- [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)
- [Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05696/) (2021)

## Abstract (arXiv)

In the Correlation Clustering problem, we are given a set of objects with pairwise similarity information. Our aim is to partition these objects into clusters that match this information as closely as possible. More specifically, the pairwise information is given as a weighted graph G with its edges labelled as ``similar" or ``dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of ``disagreements": the sum of the weights of similar edges across clusters and dissimilar edges within clusters. In this exposition we focus on the case when G is complete and unweighted. We explore four approximation algorithms for the Correlation Clustering problem under this assumption. In particular, we describe the following algorithms: (i) the 17429-approximation algorithm by Bansal, Blum, and Chawla, (ii) the 4-approximation algorithm by Charikar, Guruswami, and Wirth (iii) the 3-approximation algorithm by Ailon, Charikar, and Newman (iv) the 2.06-approximation algorithm by Chawla, Makarychev, Schramm, and Yaroslavtsev.