The Power of Uniform Sampling for Coresets (Xuan Wu)


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 introduce a meta-theorem for designing coresets for constrained-clustering problems. The meta-theorem reduces the task of coreset construction to one on a bounded number of ring instances with a much-relaxed additive error. This enables us to use uniform sampling, in contrast to the widely-used importance sampling, when constructing our coreset, and consequently we can easily handle constrained objectives. Notably and perhaps surprisingly, we show that this simpler sampling scheme can yield bounds that are independent of n.


Our technique yields better coreset bounds, and sometimes the first coreset, for many constrained clustering problems, including capacitated clustering, fair clustering, Euclidean Wasserstein barycenter, clustering in minor-excluded graph, and polygon clustering under Fr'{e}chet and Hausdorff distance. Finally, our technique also yields improved coresets for 1-Median in low-dimensional Euclidean spaces, specifically of size

\tilde{O}(eps^{-1.5}) in R^2.


This work is joint work with Vladimir Braverman, Vincent Cohen-Addad, Shaofeng Jiang, Robert Krauthgamer, and Mads Bech Toftrup.


2022-08-02  13:30 - 14:30   


Xuan Wu,  Huawei Tcs Lab


Tencent meeting ID: 853-8759-9058; PW: 123456