TY - GEN

T1 - Algorithms for stable and perturbation-resilient problems

AU - Angelidakis, Haris

AU - Makarychev, Konstantin

AU - Makarychev, Yury

N1 - Publisher Copyright:
© 2017 Copyright held by the owner/author(s).
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2017/6/19

Y1 - 2017/6/19

N2 - We study the notion of stability and perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Shef-fet (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 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 + √2 ≈ 2.41 perturbation-resilient instances. Our result is tight in the sense that no polynomial-time algorithm can solve (2 - ϵ)-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 + δ)-weakly stable instances of Minimum Multiway Cut. Finally, we show that there are no robust polynomial-time algorithms for n1-ϵ -stable instances of Set Cover, Minimum Vertex Cover, and Min 2-Horn Deletion (unless P = NP).

AB - We study the notion of stability and perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Shef-fet (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 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 + √2 ≈ 2.41 perturbation-resilient instances. Our result is tight in the sense that no polynomial-time algorithm can solve (2 - ϵ)-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 + δ)-weakly stable instances of Minimum Multiway Cut. Finally, we show that there are no robust polynomial-time algorithms for n1-ϵ -stable instances of Set Cover, Minimum Vertex Cover, and Min 2-Horn Deletion (unless P = NP).

KW - K-means

KW - K-median

KW - Perturbation resilience and stability

UR - http://www.scopus.com/inward/record.url?scp=85024364638&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85024364638&partnerID=8YFLogxK

U2 - 10.1145/3055399.3055487

DO - 10.1145/3055399.3055487

M3 - Conference contribution

AN - SCOPUS:85024364638

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 438

EP - 451

BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

A2 - McKenzie, Pierre

A2 - King, Valerie

A2 - Hatami, Hamed

PB - Association for Computing Machinery

T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017

Y2 - 19 June 2017 through 23 June 2017

ER -