Correlation Clustering with Noisy Partial Information

2014/06/22 by Konstantin Makarychev, Makarychev, Konstantin, Yury Makarychev +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #cs.DS #cs.LG

paper · pdf · doi:10.48550/arxiv.1406.5667

To appear at Conference on Learning Theory (COLT) 2015. Substantial changes from previous version, including a new section on recovery of the ground truth clustering. 20 pages

arxiv created 2015/05/12 · arxiv updated 2015/05/13

Abstract

In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clustering instances from this model. The first algorithm finds a solution of value (1+ δ) optcost + O_δ(nlog³ n) with high probability, where optcost is the value of the optimal solution (for every δ> 0). The second algorithm finds the ground truth clustering with an arbitrarily small classification error η (under some additional assumptions on the instance).

Related

• Robust Correlation Clustering with Asymmetric Noise
• Four Algorithms for Correlation Clustering: A Survey
• Better Private Algorithms for Correlation Clustering
• Understanding the Cluster LP for Correlation Clustering
• An FPT Constant-Factor Approximation Algorithm for Correlation Clustering