A generic framework for coreset construction was suggested in [1]}. The main technique is a reduction from coreset to \(\varepsilon \) -approximations, that can be computed using non-uniform sampling. The distribution of the sampling is based on the importance of each point (in some well defined sense), and the size of the coreset depends on the sum of these importance levels. This term of importance appeared in the literature as leverage score (in the context of low-rank approximation, see [2]} and references therein), or, for the case of \(k\) -clustering, sensitivity [3]}. The proof of many previous coreset constructions were significantly simplified by using this framework, and maybe more importantly, the size of these coresets was sometimes significantly reduced; see [1]} for references. Many of these coresets size can be further improve by our improved framework, as explained below.
