Pivot based correlation clustering in the presence of good clusters
This work provides an incremental improvement to correlation clustering algorithms, addressing a specific bottleneck in approximation theory for researchers in theoretical computer science.
The paper tackles the problem of improving the approximation ratio of the classic pivot-based correlation clustering algorithm by removing good clusters before each pivot step, achieving a new ratio of 2.9991. It demonstrates the algorithm's effectiveness on synthetic datasets, showing improvements over existing methods.
The classic pivot based clustering algorithm of Ailon, Charikar and Chawla [JACM'08] is factor 3, but all concrete examples showing that it is no better than 3 are based on some very good clusters, e.g., a complete graph minus a matching. By removing all good clusters before we make each pivot step, we show that this improves the approximation ratio to $2.9991$. To aid in this, we also show how our proposed algorithm performs on synthetic datasets, where the algorithm performs remarkably well, and shows improvements over both the algorithm for locating good clusters and the classic pivot algorithm.