Correlation Clustering with Noisy Partial Information
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+ δ)\mathrm{opt-cost} + O_δ(n\log^3 n) with high probability, where \mathrm{opt-cost} 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).
Cite
Text
Makarychev et al. "Correlation Clustering with Noisy Partial Information." Annual Conference on Computational Learning Theory, 2015.Markdown
[Makarychev et al. "Correlation Clustering with Noisy Partial Information." Annual Conference on Computational Learning Theory, 2015.](https://mlanthology.org/colt/2015/makarychev2015colt-correlation/)BibTeX
@inproceedings{makarychev2015colt-correlation,
title = {{Correlation Clustering with Noisy Partial Information}},
author = {Makarychev, Konstantin and Makarychev, Yury and Vijayaraghavan, Aravindan},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2015},
pages = {1321-1342},
url = {https://mlanthology.org/colt/2015/makarychev2015colt-correlation/}
}