paper

Towards Tight Robust Coresets for -Medians Clustering

arXiv:2507.11260

Abstract

This paper considers coresets for the robust -medians problem with outliers, and new constructions in various metric spaces are obtained. Specifically, for metric spaces with a bounded VC or doubling dimension , the coreset size is , which is optimal up to logarithmic factors. For Euclidean spaces, the coreset size is , improving upon a recent result by Jiang and Lou (ICALP 2025). These results also extend to robust -clustering, yielding, for VC and doubling dimension, a coreset size of with the optimal linear dependence on . This extended result improves upon the earlier work of Huang et al. (SODA 2025). The techniques introduce novel dataset decompositions, enabling chaining arguments to be applied jointly across multiple components.