This paper considers the model introduced by Bilu and Linial (2010), who studied problems for which the optimal clustering does not change when the distances are perturbed by multiplicative factors. They showed that even when a problem is NP-hard, it is sometimes possible to obtain polynomial-time algorithms for instances resilient to large perturbations, e.g.\ on the order of $O(\sqrt{n})$ for max-cut clustering. Awasthi et al. (2010) extended this line of work by considering center-based objectives, and Balcan and Liang (2011) considered the $k$-median and min-sum objectives, giving efficient algorithms for instances resilient to certain constant multiplicative perturbations. Yet, the actual assumptions required for all these algorithms to work are unrealistic for real-world data, and our paper shows there is little room to improve these results for natural stability assumptions by giving NP-hardness lower bounds for both the $k$-median and min-sum objectives. Furthermore, we show that multiplicative resilience parameters, even only on the order of $\Theta(1)$, can be so strong as to make the clustering problem trivial, and we exploit these assumptions to present a simple one-pass streaming algorithm for the $k$-median objective. We also consider a model of additive perturbations and give a correspondence between additive and multiplicative notions of stability. Our results, taken together, serve to cast doubt on the usefulness of data stability assumptions.

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

聚类中的数据稳定性：深入研究