We study the notion of stability and perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is α-stable or α-perturbation-resilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most α. In this paper, we give improved algorithms for stable instances of various clustering and combinatorial optimization problems. We also prove several hardness results. We rst give an exact algorithm for 2-perturbation resilient instances of clustering problems with natural center-based objectives. The class of clustering problems with natural center-based objectives includes such problems as k-means, k-median, and k-center. Our result improves upon the result of Balcan and Liang (2016), who gave an algorithm for clustering 1 + √ 2 ≈ 2.41 perturbationresilient instances. Our result is tight in the sense that no polynomialtime algorithm can solve (2 − ε )-perturbation resilient instances of k-center unless N P = RP, as was shown by Balcan, Haghtalab, and White (2016). We then give an exact algorithm for (2 − 2/k )-stable instances of Minimum Multiway Cut with k terminals, improving the previous result of Makarychev, Makarychev, and Vijayaraghavan (2014), who gave an algorithm for 4-stable instances. We also give an algorithm for (2 − 2/k + δ )-weakly stable instances of Minimum Multiway Cut. Finally, we show that there are no robust polynomial-time algorithms for n 1−ε -stable instances of Set Cover, Minimum Vertex Cover, and Min 2-Horn Deletion (unless P = N P). • Theory of computation → Facility location and clustering; KEYWORDS perturbation resilience and stability, k-median, k-means ACM Reference format: Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev. 2017.
Recently, Angelidakis et al. REF , gave an unifying algorithm which gives exact solution for 2-perturbation resilient instances of clustering problems with center based objectives.
Algorithms for stable and perturbation-resilient problems
STOC 2017
Computer Science Mathematics