A Tight VC-Dimension Analysis of Clustering Coresets with Applications

Vincent Cohen-Addad, Andrew Draganov, Matteo Russo +2

We consider coresets for $k$-clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the $k$-median objective $\sum_…