📄 Conference Paper
A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions
242
Citations
2
Authors
15
References
1
Countries
Abstract
We present the first linear time (1 + /spl epsiv/)-approximation algorithm for the k-means problem for fixed k and /spl epsiv/. 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.
Authors (2) 1 from IIT Delhi
Publication Details
| Type | Conference Paper |
|---|---|
| Published | December 23, 2004 |
| Source | Annual Symposium on Foundations of Computer Science |
| Publisher | Institute of Electrical and Electronics Engineers |
| DOI | 10.1109/focs.2004.7 |
| OpenAlex ID | W2110105238 |
| Open Access | Closed Access |
Research Topics
Related Publications