A Composable Coreset for k-Center in Doubling Metrics

A set of points P in a metric space and a constant integer k are given. The k-center problem finds k points as centers among P, such that the maximum distance of any point of P to their closest centers (r) is minimized. Doubling metrics are metric spaces in which for any r, a ball of radius r can be covered using a constant number of balls of radius r/2. Fixed dimensional Euclidean spaces are doubling metrics. The lower bound on the approximation factor of k-center is 1.822 in Euclidean spaces, however, (1+ε)-approximation algorithms with exponential dependency on frac1ε and k exist. For a given set of sets P1,ldots,PL, a composable coreset independently computes subsets C1subset P1, ldots, CLsubset PL, such that cupi=1L Ci contains an approximation of a measure of the set cupi=1L Pi. We introduce a (1+ε)-approximation composable coreset for k-center, which in doubling metrics has size sublinear in |P|. This results in a (2+ε)-approximation algorithm for k-center in MapReduce with a constant number of rounds in doubling metrics for any ε>0 and sublinear communications, which is based on parametric pruning. We prove the exponential nature of the trade-off between the number of centers (k) and the radius (r), and give a composable coreset for a related problem called dual clustering. Also, we give a new version of the parametric pruning algorithm with O(fracnkε) running time, O(n) space and 2+ε approximation factor for metric k-center.