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

2023/05/23 by Sayak Chakrabarty, Chakrabarty, Sayak, Konstantin Makarychev +1 · 4 citations
Computer Science · Mathematics · #Advanced Clustering Algorithms Research #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2305.13560

openalex publication_date 2023/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• A Simple and Fast (3+ε)-approximation for Constrained Correlation Clustering
• Learning-Augmented Streaming Algorithms for Correlation Clustering
• SPARSE-PIVOT: Dynamic correlation clustering for node insertions
• CLT and Edgeworth Expansion for m-out-of-n Bootstrap Estimators of The Studentized Median

Related

• Correlation Clustering Beyond the Pivot Algorithm
• Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
• SPARSE-PIVOT: Dynamic correlation clustering for node insertions
• Almost 3-Approximate Correlation Clustering in Constant Rounds
• Efficient Correlation Clustering Methods for Large Consensus Clustering Instances