# Correlation Clustering with Noisy Partial Information

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).