Sublinear-time approximation algorithms for clustering via random sampling
CzumajArtur, SohlerChristian · Random Structures and Algorithms · 2007
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...