2016/07/21 by Konstantin Makarychev, Makarychev, Konstantin, Yury Makarychev +1
Engineering · #Infrastructure Resilience and Vulnerability Analysis
paper · pdf · doi:10.48550/arxiv.1607.06442
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-ε)-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.