1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
By: Dahoon Lee, Chenglin Fan, Euiwoong Lee
Potential Business Impact:
Finds better ways to group things with many connections.
Chromatic Correlation Clustering (CCC) generalizes Correlation Clustering by assigning multiple categorical relationships (colors) to edges and imposing chromatic constraints on the clusters. Unlike traditional Correlation Clustering, which only deals with binary $(+/-)$ relationships, CCC captures richer relational structures. Despite its importance, improving the approximation for CCC has been difficult due to the limitations of standard LP relaxations. We present a randomized $1.64$-approximation algorithm to the CCC problem, significantly improving the previous factor of $2.15$. Our approach extends the cluster LP framework to the chromatic setting by introducing a chromatic cluster LP relaxation and an rounding algorithm that utilizes both a cluster-based and a greedy pivot-based strategy. The analysis bypasses the integrality gap of $2$ for the CCC version of standard LP and highlights the potential of the cluster LP framework to address other variants of clustering problems.
Similar Papers
Chromatic correlation clustering via cluster LP
Data Structures and Algorithms
Helps group similar things better with new math.
Constrained Centroid Clustering: A Novel Approach for Compact and Structured Partitioning
Machine Learning (CS)
Groups data points tightly, like a neat circle.
Solving the Correlation Cluster LP in Sublinear Time
Data Structures and Algorithms
Groups similar things together better and faster.