Improved approximation algorithm for the k-means clustering problem
Shiying Shi · Journal of Shandong University · 2011
The(1+e)-randomized approximation algorithm proposed by Ostrovsky was investigated in depth,and an improved algorithm was proposed.The sample parameter was enlarged to reduce the size of sample set.Based on the randomized algorithm,a new method was proposed to decrease the enumerating number.Also,the successful probability of the improved algorithm was analyzed.The running time of the improved algorithm was O2Okα2end,where d,n denote the dimension and the number of the input points respectively,and α represents the separated coefficient that is lower than 1.The probability was 121-e-12ek(1-O(α)).Compared to the original algorithm,the improved algorithm runs more efficiency.