Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
Nairen Cao, Shang-En Huang, Hsin-Hao Su · Society for Industrial and Applied Mathematics eBooks · 2024
In this paper, we study parallel algorithms for the correlation clustering problem, where every pair of two different entities is labeled with similar or dissimilar. The goal is to partition the entities into clusters to minimize the number of disagreements with the labels. Currently, all efficient parallel algorithms have an approximation ratio of at least 3. In comparison with the 1.994 + ɛ ratio achieved by polynomial-time sequential algorithms [25], a significant gap exists.