Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

Correlation Clustering with Noisy Partial Information

Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
Proceedings of The 28th Conference on Learning Theory, pp. 1321–1342, 2015

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+ \delta)\mathrm{opt-cost} + O_{\delta}(n\log^3 n)\) with high probability, where \(\mathrm{opt-cost}\) 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).

Related Material