An improved PTAS approximation algorithm for k-means clustering problem

摘要

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.