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

We give an improved analysis of the simple D2-sampling based PTAS for the k-means clustering problem given by Jaiswal et al. [3]. The improvement on the running time is from O(nd⋅2O˜(k2/ϵ)) to O(nd⋅2O˜(k/ϵ)).