Correlation Clustering with Noisy Partial Information

author: Aravindan Vijayaraghavan, Courant Institute of Mathematical Sciences, New York University (NYU)
published: Aug. 20, 2015,   recorded: July 2015,   views: 12
Categories

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Description

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+ \delta)optcost + O_{\delta}(n\log^3 n)$ with high probability, where \optcost is the value of the optimal solution (for every $\delta > 0$). The second algorithm finds the ground truth clustering with an arbitrarily small classification error $\eta$ (under some additional assumptions on the instance).