Algorithms for stable and perturbation-resilient problems Article Swipe

PDF

Related Concepts

Perturbation (astronomy) Cluster analysis Computer science Combinatorial optimization Resilience (materials science) Mathematical optimization Combinatorial algorithms Optimization problem Combinatorial explosion Algorithm Stability (learning theory) Theoretical computer science Parallel computing Mathematics Combinatorics Materials science Artificial intelligence Physics Machine learning Composite material Quantum mechanics

Haris Angelidakis , Konstantin Makarychev , Yury Makarychev ·

YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.1145/3055399.3055487 · OA: W2626597900

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.