(1+ε)-Approximation Algorithm for k-means
Shouqiang Wang · Modern Electronics Technique · 2006
This paper introduces an improvement algorithm given by Amit Kumar for the problem of k-means.This improvement algorithm can get a higher probability for success in the process of sampling.This algorithm running time can be regarded as linear when fixed k and e.After running this algorithm several times,we can get a higher probability to the ratio of(1+e)-approximation for the k-means problem.