# Dynamic clustering to minimize the sum of radii

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2017.

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

- [Dynamic algorithms for k-center on graphs](https://mlsanity.com/paper/2307.15557/) (2023)
- [Approximating Fair k-Min-Sum-Radii in Euclidean Space](https://mlsanity.com/paper/2309.00834/) (2023)

## Abstract (arXiv)

In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem.