Abstract
In this paper, we show that there exists a (k, ε)-coreset for k-median and k-means clustering of n points in ℝd, which is of size independent of n. In particular, we construct a (k, ε)-coreset of size O(k2/εd) for k-median clustering, and of size O(k3/εd+1) for k-means clustering.
Original language | English (US) |
---|---|
Pages | 126-134 |
Number of pages | 9 |
DOIs | |
State | Published - 2005 |
Event | 21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy Duration: Jun 6 2005 → Jun 8 2005 |
Other
Other | 21st Annual Symposium on Computational Geometry, SCG'05 |
---|---|
Country/Territory | Italy |
City | Pisa |
Period | 6/6/05 → 6/8/05 |
Keywords
- Clustering
- Coresets
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics