In the \(k\) -means problem we wish to compute a set \(k\)  of centers (points) in some metric space, such that the sum of squared distances to the input points is minimized, where each input point is assigned to its nearest center. The corresponding coreset is a positively weighted subset of points that approximates this cost to every given set of \(k\)  centers. First deterministic coresets of size exponential in \(d\)  were first suggested by Har-Peled and Mazumdar in [1]}. The first coreset construction of size polynomial in \(d\)  was suggested by Ke-Chen in [2]} using several sets of uniform sampling.
