Chromatic correlation clustering via cluster LP
By: Fateme Abbasi , Hyung-Chan An , Jarosław Byrka and more
Potential Business Impact:
Helps group similar things better with new math.
Correlation Clustering is a fundamental clustering problem, and there has been a line of work on improving the approximation ratio for this problem in recent years. A key algorithmic component in these works is the cluster LP. Chromatic Correlation Clustering is an interesting generalization that has also been intensively studied. In light of success of the cluster LP in Correlation Clustering, it would be an interesting question whether the cluster LP can be used in Chromatic Correlation Clustering. We answer this question with affirmatives by presenting a $(2+\varepsilon)$-approximation algorithm for Chromatic Correlation Clustering using a chromatic cluster LP.
Similar Papers
1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
Data Structures and Algorithms
Finds better ways to group things with many connections.
Solving the Correlation Cluster LP in Sublinear Time
Data Structures and Algorithms
Groups similar things together better and faster.
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Data Structures and Algorithms
Makes computer grouping work faster on big data.