A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Amit Kumar Articles by Yogish Sabharwal Articles by Sandeep Sen

45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)

Rome, Italy

October 17-October 19

ISBN: 0-7695-2228-9

	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

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.7

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.