Stability yields a ptas for k-median and k-means clustering

Abstract—We consider k-median clustering in finite metric spaces and k-means clustering in Euclidean spaces, in the setting where k is part of the input (not a constant). For the k-means problem, Ostrovsky et al. [18] show that if the optimal (k−1)-means clustering of the input is more expensive than the optimal k-means clustering by a factor of 1/ǫ2, then one can achieve a (1 + f(ǫ))-approximation to the k-means optimal in time polynomial in n and k by using a variant of Lloyd’s algorithm. In this work we substantially improve this approximation guarantee. We show that given only the condition that the (k−1)-means optimal is more expensive than the k-means optimal by a factor 1+α for some constant α> 0, we can obtain a PTAS. In particular, under this assumption, for any ǫ> 0 we achieve a (1 + ǫ)-approximation to the k-means optimal in time polynomial in n and k, and exponential i