Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
Journal
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Part Of
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Journal Volume
2024-January
Start Page
4124
End Page
4154
ISBN
9781611977912
Date Issued
2024-01
Author(s)
Abstract
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.
SDGs
Publisher
Society for Industrial and Applied Mathematics
Type
conference paper