Metric Perturbation Resilience

We study the notion of perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A clustering problem is α-perturbation resilient if the optimal clustering does not change when we perturb all distances by a factor of at most α. We consider a class of clustering problems with center-based objectives, which includes such problems as k-means, k-median, and k-center, and give an exact algorithm for clustering 2-perturbation resilient instances. Our result improves upon the result of Balcan and Liang (2016), who gave an algorithm for clustering 1+√2≈ 2.41 perturbation resilient instances. Our result is tight in the sense that no polynomial-time algorithm can solve (2-varepsilon)-perturbation resilient instances unless NP = RP, as was shown by Balcan, Haghtalab, and White (2016). We show that the algorithm works on instances satisfying a slightly weaker and more natural condition than perturbation resilience, which we call metric perturbation resilience.