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^{2})/(µ^{d})) for k-median
clustering, and of size O((k^{3})/(µ^{d+1}))
for k-means clustering.