The Power of Uniform Sampling for Coresets

Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H. -C. Jiang +4

Motivated by practical generalizations of the classic $k$-median and $k$-means objectives, such as clustering with size constraints, fair clustering, and Wasserstein barycenter, we…