Algorithms for Stable and Perturbation-Resilient Problems

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 alpha-stable or alpha-perturbation-resilient if the optimal solution does not change whenwe perturb all parameters of the problem by a factor of at most alpha. In this paper, we give improved algorithms for stable instances of various clustering and combinatorial optimization problems. We also prove several hardness results. We First 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 + root 2 approximate to 2 : 41 perturbation-resilient instances. Our result is tight in the sense that no polynomialtime algorithm can solve (2 - epsilon)-perturbation resilient instances of k-center unless NP = 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 + delta)-weakly stable instances of Minimum Multiway Cut. Finally, we show that there are no robust polynomial-time algorithms for n(1-epsilon) -stable instances of Set Cover, Minimum Vertex Cover, and Min 2-Horn Deletion (unless P = NP).