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

45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04) pp. 454-462
A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions
Amit Kumar, IIT Delhi
Yogish Sabharwal, IBM India Research Lab and IIT Delhi
Sandeep Sen, IIT Delhi

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.7
Send link to a friend

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.
Back to Top Additional Information
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

	Advanced Search
CS Search Google Search