Kumar, A. ; Sabharwal, Y. ; Sen, S. (2004) A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions In: 45th Annual IEEE Symposium on Foundations of Computer Science, 17-19 Oct. 2004, Rome, Italy.
Full text not available from this repository.
Official URL: http://doi.org/10.1109/FOCS.2004.7
Related URL: http://dx.doi.org/10.1109/FOCS.2004.7
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.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Institute of Electrical and Electronic Engineers. |
| ID Code: | 123551 |
| Deposited On: | 30 Sep 2021 10:26 |
| Last Modified: | 30 Sep 2021 10:26 |
Repository Staff Only: item control page
