# A Composable Coreset for k-Center in Doubling Metrics

arXiv: https://arxiv.org/abs/1902.01896 · HTML: https://mlsanity.com/paper/1902.01896/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2019.

## Built on by (most cited first, 1 of 1)

- [Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers](https://mlsanity.com/paper/2301.02814/) (2023)

## Abstract (arXiv)

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.