Correlation Clustering with Noisy Partial Information
This work addresses clustering challenges in noisy, partially observed data, representing an incremental improvement with specific algorithmic guarantees.
The paper tackles the Correlation Clustering problem on arbitrary graphs under a semi-random model with noisy partial information, proposing two approximation algorithms: one achieves a solution value of (1+δ)optcost + O_δ(n log^3 n) with high probability, and the other recovers the ground truth clustering with arbitrarily small classification error η under additional assumptions.
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_δ(n\log^3 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).