Algorithms for stable and perturbation-resilient problems

Haris Angelidakis, Konstantin Makarychev, Yury Makarychev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

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).

Original languageEnglish (US)
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
EditorsPierre McKenzie, Valerie King, Hamed Hatami
PublisherAssociation for Computing Machinery
Pages438-451
Number of pages14
ISBN (Electronic)9781450345286
DOIs
StatePublished - Jun 19 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: Jun 19 2017Jun 23 2017

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F128415
ISSN (Print)0737-8017

Other

Other49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
CountryCanada
CityMontreal
Period6/19/176/23/17

Keywords

  • K-means
  • K-median
  • Perturbation resilience and stability

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Algorithms for stable and perturbation-resilient problems'. Together they form a unique fingerprint.

Cite this