Fully Dynamic Clustering and Diversity Maximization in Doubling Metrics

We present approximation algorithms for some variants of k-center clustering and diversity maximization in a fully dynamic setting, where the active pointset evolves through arbitrary insertions and deletions. All algorithms employ a coreset-based strategy and rely on the use of the cover tree data structure, which we crucially augment to maintain, at any time, some additional information enabling the efficient extraction of the solution for the specific problem. For all the problems under consideration, our algorithms compute (α+ϵ)-approximate solutions, where is the best-known approximation attainable in polynomial time in the standard static setting, and ϵ > 0 is a user-provided accuracy parameter. Remarkably, and unlike previous works, the (cover tree) data structure used by our algorithms and the running times of the update procedures are both independent of the accuracy parameter and, for the k-center variants, also of parameter k. The analysis is performed in terms of the doubli...