mlsanityData to 14 Oct 2026

Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!

arXiv 2305.13560 ↗First posted 23 May 2023cs.DS cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

We show that a simple single-pass semi-streaming variant of the Pivot algorithm for Correlation Clustering gives a (3 + ε)-approximation using O(n/ε) words of memory. This is a slight improvement over the recent results of Cambus, Kuhn, Lindy, Pai, and Uitto, who gave a (3 + ε)-approximation using O(n log n) words of memory, and Behnezhad, Charikar, Ma, and Tan, who gave a 5-approximation using O(n) words of memory. One of the main contributions of this paper is that both the algorithm and its analysis are very simple, and also the algorithm is easy to implement.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 23 of its 45 references that are in the map. First posted on arXiv 23 May 2023.

Builds on

23 of 45 references.

References · 23

  1. 2018Fair Clustering Through Fairletscited by 176
  2. 2014Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphscited by 27
  3. 2020Fair Correlation Clusteringcited by 27
  4. 2021Correlation Clustering in Constant Many Parallel Roundscited by 15
  5. 2022Correlation Clustering with Sherali-Adamscited by 15
  6. 2015Parallel Correlation Clustering on Big Graphscited by 14
  7. 2017Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clusteringcited by 12
  8. 2021Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Boundscited by 12
  9. 2015Correlation Clustering and Biclustering with Locally Bounded Errorscited by 9
  10. 2021Scalable Community Detection via Parallel Correlation Clusteringcited by 9
  11. 2017Local Guarantees in Graph Cuts and Clusteringcited by 8
  12. 2018Correlation Clustering in Data Streamscited by 7
11 more
  1. 2021Local Correlation Clustering with Asymmetric Classification Errorscited by 7
  2. 2021Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositionscited by 7
  3. 2023Fast Combinatorial Algorithms for Min Max Correlation Clusteringcited by 7
  4. 2021Correlation Clustering with Asymmetric Classification Errorscited by 6
  5. 2022Almost 3-Approximate Correlation Clustering in Constant Roundscited by 6
  6. 2022Improved Approximation for Fair Correlation Clusteringcited by 6
  7. 2019Min-Max Correlation Clustering via MultiCutcited by 5
  8. 2021Massively Parallel Correlation Clustering in Bounded Arboricity Graphscited by 4
  9. 2017Tight Analysis of Randomized Greedy MIScited by 3
  10. 2017Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under ℓp-Distancescited by 3
  11. 2018Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Covercited by 2

Built on by

Cited by year (2026 to 14 Oct)

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

8 papers.

  1. 2024Free and Customizable Code Documentation with LLMs: A Fine-Tuning Approachcited by 10
  2. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  3. 2024MM-PoE: Multiple Choice Reasoning via. Process of Elimination using Multi-Modal Modelscited by 5
  4. 2025CLT and Edgeworth Expansion for m-out-of-n Bootstrap Estimators of The Studentized Mediancited by 2
  5. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  6. 2024Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Timecited by 0
  7. 2026Is Sliding Window All You Need? An Open Framework for Long-Sequence Recommendationcited by 0
  8. 2026Inductive Correlation Clustering with Graph Neural Networkscited by 0