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

We give an improved analysis of the simple D 2 -sampling based PTAS for the k-means clustering problem given by Jaiswal et al. 3. The improvement on the running time is from O ( n d ? 2 O ? ( k 2 / ? ) ) to O ( n d ? 2 O ? ( k / ? ) ) . We give improved analysis of the Jaiswal-Kumar-Sen algorithm 3.We get a better running time bound using our analysis.The new analysis does not require the irreducibility property.