Home Bookmarks Papers Blog

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 Rd, 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.

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 Jan 11 13:15:48 CST 2015