2025/02/11 by Jiang, Shaofeng H. -C., Lou, Jianing
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.07669
We devise ε-coresets for robust (k,z)-Clustering with m outliers through black-box reductions to vanilla case. Given an ε-coreset construction for vanilla clustering with size N, we construct coresets of size N⋅ polylog(kmε-1) + Oz(min\kmε-1, mε-2zlogz(kmε-1) \) for various metric spaces, where Oz hides 2O(zlog z) factors. This increases the size of the vanilla coreset by a small multiplicative factor of polylog(kmε-1), and the additive term is up to a (ε-1log (km))O(z) factor to the size of the optimal robust coreset. Plugging in vanilla coreset results of [Cohen-Addad et al., STOC'21], we obtain the first coresets for (k,z)-Clustering with m outliers with size near-linear in k while previous results have size at least Ω(k2) [Huang et al., ICLR'23; Huang et al., SODA'25]. Technically, we establish two conditions under which a vanilla coreset is as well a robust coreset. The first condition requires the dataset to satisfy special structures - it can be broken into "dense" parts with bounded diameter. We combine this with a new bounded-diameter decomposition that has only Oz(km ε-1) non-dense points to obtain the Oz(km ε-1) additive bound. Another condition requires the vanilla coreset to possess an extra size-preserving property. We further give a black-box reduction that turns a vanilla coreset to the one satisfying the said size-preserving property, leading to the alternative Oz(mε-2zlogz(kmε-1)) additive bound. We also implement our reductions in the dynamic streaming setting and obtain the first streaming algorithms for k-Median and k-Means with m outliers, using space O(k+m)\cdotpoly(dε-1logΔ) for inputs on the grid [Δ]d.