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

Ragesh Jaiswal, Mehul Kumar, Pulkit Yadav

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…