loading...
A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions
Rome, Italy October 17-October 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.745th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Amit Kumar, Yogish Sabharwal, Sandeep Sen, "A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions," Foundations of Computer Science, Annual IEEE Symposium on, pp. 454-462, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.7,
author = {Amit Kumar and Yogish Sabharwal and Sandeep Sen},
title = {A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {454-462},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.7},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions
SN - 0272-5428
SP454
EP462
A1 - Amit Kumar,
A1 - Yogish Sabharwal,
A1 - Sandeep Sen,
PY - 2004
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Amit Kumar, IIT Delhi
Yogish Sabharwal, IBM India Research Lab and IIT Delhi
Sandeep Sen, IIT Delhi
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.
Citation:
Amit Kumar, Yogish Sabharwal, Sandeep Sen, "A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions," focs, pp.454-462, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.