Skip to yearly menu bar Skip to main content


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

Konstantin Makarychev · Sayak Chakrabarty

Great Hall & Hall B1+B2 (level 1) #1915
[ ]
Thu 14 Dec 8:45 a.m. PST — 10:45 a.m. PST


We show that a simple single-pass semi-streaming variant of the Pivot algorithm for Correlation Clustering gives a (3+eps)-approximation using O(n/eps) words of memory. This is a slight improvement over the recent results of Cambus, Kuhn, Lindy, Pai, and Uitto, who gave a (3+eps)-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 our paper is that the algorithm and its analysis are simple and easy to understand.

Chat is not available.