International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong


Invited Speakers

Young Faculty Forum in TCS

The Power of Uniform Sampling for Coresets

Xuan Wu

Huawei TCS Lab

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 a large number of constrained clustering problems, including capacitated clustering, fair clustering, Euclidean Wasserstein barycenter, clustering in minor-excluded graph, and polygon clustering under Fréchet and Hausdorff distance. Finally, our technique also yields improved coresets for 1-Median in low-dimensional Euclidean spaces, of size \tilde{O}(eps^{-1.5}) in R^2, breaking the natural eps^{-2} barrier.
Joint work with Vladimir Braverman, Vincent Cohen-Addad, Shaofeng Jiang, Robert Krauthgamer, and Mads Bech Toftrup.

Xuan Wu is currently a researcher in Huawei TCS Lab, led by Prof. Pinyan Lu. He earned his Ph.D. degree from Johns Hopkins University, advised by Prof. Vladimir Braverman. Previously, he earned his Master's degree from IIIS and Bachelor's degree from Yao Class, both advised by Prof. Jian Li, at Tsinghua University.