Optical Core-Sets for Balls

This paper shows that any point set has an e-core-set of size [1/e], and this bound is tight in the worst case. A faster algorithm given here finds an e-core-set of size at most 2/e. These results imply the existence of small core-sets for solving approximate k-center clustering and related problems. The sizes of these core-sets are considerably smaller than the previously known bounds, and imply faster algorithms.