We give a sampling-based algorithm for the k-Median problem, with running time O(k(k 2 log k) 2 log (k log k)), where k is the desired number of clusters and is a confidence parameter. This is the first k-Median algorithm ...