The Power of Uniform Sampling for $k$-Median

Lingxiao Huang, Shaofeng H. -C. Jiang, Jianing Lou

We study the power of uniform sampling for $k$-Median in various metric spaces. We relate the query complexity for approximating $k$-Median, to a key parameter of the dataset, call…