Improved analysis of D2-sampling based PTAS for k-means and other Clustering problems

Abstract

We give an improved analysis of the simple $D^2$-sampling based PTAS for the $k$-means clustering problem given by Jaiswal, Kumar, and Sen (Algorithmica, 2013). The improvement on the running time is from $O\left(nd\cdot 2^{\tilde{O}(k^2/\epsilon )}\right)$ to $O\left(nd\cdot 2^{\tilde{O}(k/\epsilon )}\right)$.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1201.4206