Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
This work provides an incremental improvement for researchers in streaming algorithms and clustering, focusing on memory efficiency in large-scale data processing.
The paper tackles the problem of correlation clustering in a semi-streaming setting by proposing a single-pass variant of the Pivot algorithm, achieving a (3 + ε)-approximation using O(n/ε) words of memory, which slightly improves over prior results in memory usage.
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.