In this paper, we show that there exists a (k, ε)-coreset for k-median and k-means clustering of n points in IR 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.
Har-Peled and Kushal REF later developed coresets of size O(k 2 ǫ −d ) for k-median and k-means problems.
Smaller coresets for k-median and k-means clustering
Computer Science Mathematics