# Metric Perturbation Resilience

arXiv: https://arxiv.org/abs/1607.06442 · HTML: https://mlsanity.com/paper/1607.06442/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2016.

## Built on by (most cited first, 2 of 2)

- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)

## Abstract (arXiv)

We study the notion of perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A clustering problem is α-perturbation resilient if the optimal clustering does not change when we perturb all distances by a factor of at most α. We consider a class of clustering problems with center-based objectives, which includes such problems as k-means, k-median, and k-center, and give an exact algorithm for clustering 2-perturbation resilient instances. 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-varepsilon)-perturbation resilient instances unless NP = RP, as was shown by Balcan, Haghtalab, and White (2016). We show that the algorithm works on instances satisfying a slightly weaker and more natural condition than perturbation resilience, which we call metric perturbation resilience.