Massively Parallel and Dynamic Algorithms for Minimum Size Clustering

Understand

In this paper, we study the $r$-gather problem, a natural formulation of minimum-size clustering in metric spaces.

• The goal of $r$-gather is to partition $n$ points into clusters such that each cluster has size at least $r$, and the maximum radius of the clusters is minimized.
• This additional constraint completely changes the algorithmic nature of the problem, and many clustering techniques fail.
• Also previous dynamic and parallel algorithms do not achieve desirable complexity.