Reviews: Clustering Stable Instances of Euclidean k-means.

The authors propose a notion of additive perturbation stability (APS) for Euclidean distances that maintain the optimal k-means clustering solution when each point in the data is moved by a sufficiently small Euclidean distance. I think the paper is rather interesting; however, the results of the paper are not very surprising. Here are my comments regarding the paper: (1) To my understanding, the results of Theorem 1.2 are only under the condition of APS. They only hold for the case of k 2 components and may lead to exponential dependence on k components for large k . However, under the additional margin condition between any two pairs of cluster, we will able to guarantee the existence of polynomial algorithm on k .