Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds

Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu +2

Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as $k$-means. Given a point set $P$, a coreset $\Omega$ is a small, weighted summ…