Smaller Coresets for $k$-Median and $k$-Means Clustering

Sariel Har-Peled. and Akash Kushal

In this paper, we show that there exists a (k,µ)-coreset for k-median and k-means clustering of n points in R^d, which is of size independent of n. In particular, we construct a (k,µ)-coreset of size O((k²)/(µ^d)) for k-median clustering, and of size O((k³)/(µ^d+1)) for k-means clustering.

Postscript, PDF.

SoCG 05 talk slides (June 7th, 2005).
Slides source.

@string{SOCG_2005 = "Proc. 21st Annu. ACM Sympos. Comput. Geom."}

@inproceedings{hk-sckmk-05,
  author       = {S. {Har-Peled} and A. Kushal},
  title        = {Smaller Coresets for $k$-Median and $k$-Means Clustering},
  note         = {\urlSarielPaper{04/small\_coreset/}},
  booktitle    = SOCG_2005,
  year         = {2005},
  pages        = {126--134}
}

Last modified: Sun Jun 26 12:01:11 CDT 2005