A simple D^2-sampling based PTAS for k-means and other Clustering Problems

Ragesh Jaiswal, Amit Kumar, Sandeep Sen

Given a set of points $P\subset {\mathbb{R}}^d$, the $k$-means clustering problem is to find a set of $k$ {\em centers} $C=\{c_1,...,c_k\},c_i\in {\mathbb{R}}^d,$ such that the ob…