We consider the model introduced by Bilu and Linial (2010), who study
problems for which the optimal clustering does not change when distances are
perturbed. They show that even when a problem is NP-hard, it is sometimes
possible to obtain efficient algorithms for instances resilient to certain
multiplicative perturbations, e.g. on the order of $O(\sqrt{n})$ for max-cut
clustering. Awasthi et al. (2010) consider center-based objectives, and Balcan
and Liang (2011) analyze the $k$-median and min-sum objectives, giving
efficient algorithms for instances resilient to certain constant multiplicative
perturbations.
Here, we are motivated by the question of to what extent these assumptions
can be relaxed while allowing for efficient algorithms. We show there is little
room to improve these results by giving NP-hardness lower bounds for both the
$k$-median and min-sum objectives. On the other hand, we show that constant
multiplicative resilience parameters can be so strong as to make the clustering
problem trivial, leaving only a narrow range of resilience parameters for which
clustering is interesting. We also consider a model of additive perturbations
and give a correspondence between additive and multiplicative notions of
stability. Our results provide a close examination of the consequences of
assuming stability in data.

本文考虑了 Bilu 和 Linial（2010）提出的模型，研究了最佳聚类不发生变化的问题，我们发现即使问题是 NP 困难的，有时候也可能获得有效算法，这些算法对于特定的多项式扰动是鲁棒的。同时，我们证明了该区间内的乘法鲁棒性参数可能太强，以至于聚类问题变得微不足道，只有一个较窄的区间是有趣的。