Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
Sayak Chakrabarty Konstantin Makarychev
We show that a simple single-pass semi-streaming variant of the Pivot
algorithm for Correlation Clustering gives a (3 + {\epsilon})-approximation
using O(n/{\epsilon}) words of memory. This is a slight improvement over the
recent results of Cambus, Kuhn, Lindy, Pai, and Uitto, who gave a (3 +
{\epsilon})-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.