Title :
An improved PTAS approximation algorithm for k-means clustering problem
Author_Institution :
Dept. of Inf. Eng., Shandong Jiaotong Univ., Jinan, China
Abstract :
This paper presented an improved (1+ε)-randomized approximation algorithm proposed by Ostrovsky. The running time of the improved algorithm is O(2(O(kα2/ε))nd), where d,n denote the dimension and the number of the input points respectively, and α(<;1) represents the separated coefficient. The successful probability is (1/2(1-e(1/2ε)))k(1-O(√α)). Compared to the original algorithm, the improved algorithm runs more efficiency.
Keywords :
approximation theory; computational complexity; pattern clustering; randomised algorithms; O(2(O(kα2/ε))nd); improved (1+ε)-randomized approximation algorithm; improved PTAS approximation algorithm; k-means clustering problem; probability; Algorithm design and analysis; Approximation algorithms; Approximation methods; Bismuth; Clustering algorithms; Partitioning algorithms; Silicon; Algorith; Centroid; Clustering; Randomized Algorithm;
Conference_Titel :
Uncertainty Reasoning and Knowledge Engineering (URKE), 2012 2nd International Conference on
Conference_Location :
Jalarta
Print_ISBN :
978-1-4673-1459-6
DOI :
10.1109/URKE.2012.6319592
