Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP
Provides the first (2+ε)-approximation for Chromatic Correlation Clustering, improving upon previous results and extending recent advances in Correlation Clustering to a more general setting.
The authors extend the cluster LP formulation to Chromatic Correlation Clustering, achieving a (2+ε)-approximation algorithm for both the standard and weighted versions of the problem.
Correlation Clustering is a fundamental clustering problem that is generalized to Chromatic Correlation Clustering to incorporate categorical data. Both problems have been intensively studied, and recently, substantial improvements were obtained in the approximation algorithms for Correlation Clustering. At the heart of this success lies a new linear program (LP) formulation called the cluster LP; a natural question was whether this LP can be extended to Chromatic Correlation Clustering to enable similar success. We answer this question in the affirmative by presenting a $(2+\varepsilon)$-approximation algorithm for the problem using a chromatic cluster LP. We then consider Weighted Chromatic Correlation Clustering, in which edges have fractional weights satisfying the probability constraints, to show that our algorithm extends to this weighted version to yield the same approximation guarantee.