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.

PDF,

Appeared in SoCG 2005, and DCG 2007.