Sublinear-time approximation algorithms for clustering via random sampling

We present a novel analysis of a random sampling approach for four clustering problems in metric spaces: k-median, k-means, min-sum k-clustering, and balanced k-median. For all these problems, we c...