Improved Coresets for Euclidean $k$-Means

Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic +2

Given a set of $n$ points in $d$ dimensions, the Euclidean $k$-means problem (resp. the Euclidean $k$-median problem) consists of finding $k$ centers such that the sum of squared d…