A Composable Coreset for k-Center in Doubling Metrics
share
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 1/ϵ and k exist. For a given set of sets P_1,...,P_L, a composable coreset independently computes subsets C_1⊂ P_1, ..., C_L⊂ P_L, such that ∪_i=1^L C_i contains an approximation of a measure of the set ∪_i=1^L P_i. 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(nk/ϵ) running time, O(n) space and 2+ϵ approximation factor for metric k-center.
READ FULL TEXT