DocumentCode
2075222
Title
A simple linear time (1 + ϵ)-approximation algorithm for k-means clustering in any dimensions
Author
Kumar, Amit ; Sabharwal, Yogish ; Sen, Sandeep
Author_Institution
Dept. of Comput. Sci. & Engg., IIT Delhi, New Delhi, India
fYear
2004
fDate
17-19 Oct. 2004
Firstpage
454
Lastpage
462
Abstract
We present the first linear time (1 + ε)-approximation algorithm for the k-means problem for fixed k and ε. Our algorithm runs in O(nd) time, which is linear in the size of the input. Another feature of our algorithm is its simplicity - the only technique involved is random sampling.
Keywords
approximation theory; computational complexity; pattern clustering; random processes; sampling methods; k-means clustering; linear time approximation algorithm; random sampling; Application software; Clustering algorithms; Computer science; Data mining; Image processing; Image retrieval; Image sampling; Information retrieval; Partitioning algorithms; Web search;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on
ISSN
0272-5428
Print_ISBN
0-7695-2228-9
Type
conf
DOI
10.1109/FOCS.2004.7
Filename
1366265
Link To Document