An improved PTAS approximation algorithm for k-means clustering problem
Wang Shouqiang · 2012
This paper presented an improved (1+ε)-randomized approximation algorithm proposed by Ostrovsky. The running time of the improved algorithm is equation, where d,n denote the dimension and the number of the input points respectively, and α(<1) represents the separated coefficient. The successful probability is equation. Compared to the original algorithm, the improved algorithm runs more efficiency.