On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications

We present new approximation algorithms for the k-median and k-means clustering problems. To this end, we obtain small coresets for k-median and k-means clustering in general metric spaces and in Euclidean spaces. In Rᵈ, these coresets are of size with polynomial dependency on the dimension d. This leads to (1+ε)-approximation algorithms to the optimal k-median and k-means clustering in Rᵈ, with running time O(ndk+2^(k/ε)O(1)d²logᵏ⁺²n), where n is the number of points. This improves over previous results. We use those coresets to maintain a (1+ε)-approximate k-median and k-means clustering of a stream of points in Rᵈ, using O(d²k²ε⁻²log⁸n) space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension.