Optimal Fully Dynamic $k$-Center Clustering for Adaptive and Oblivious Adversaries

Abstract

In fully dynamic clustering problems, a clustering of a given data set in a metric space must be maintained while it is modified through insertions and deletions of individual points. In this paper, we resolve the complexity of fully dynamic $k$-center clustering against both adaptive and oblivious adversaries. Against oblivious adversaries, we present the first algorithm for fully dynamic $k$-center in an arbitrary metric space that maintains an optimal $(2+\epsilon )$-approximation in $O(k\cdot \mathrm{polylog}(n,\Delta ))$ amortized update time. Here, $n$ is an upper bound on the number of active points at any time, and $\Delta$ is the aspect ratio of the metric space. Previously, the best known amortized update time was $O(k^2\cdot \mathrm{polylog}(n,\Delta ))$, and is due to Chan, Gourqin, and Sozio (2018). Moreover, we demonstrate that our runtime is optimal up to $\mathrm{polylog}(n,\Delta )$ factors. In fact, we prove that even offline algorithms for $k$-clustering tasks in arbitrary metric spaces, including $k$-medians, $k$-means, and $k$-center, must make at least $\Omega (nk)$ distance queries to achieve any non-trivial approximation factor. This implies a lower bound of $\Omega (k)$ which holds even for the insertions-only setting. We also show deterministic lower and upper bounds for adaptive adversaries, demonstrate that an update time sublinear in $k$ is possible against oblivious adversaries for metric spaces which admit locally sensitive hash functions (LSH) and give the first fully dynamic $O(1)$-approximation algorithms for the closely related $k$-sum-of-radii and $k$-sum-of-diameter problems.

arXiv commentarXiv admin note: substantial text overlap with arXiv:2112.07050, arXiv:2112.07217

References in corpus (7)

• Community detection in graphs
• Clustering High Dimensional Dynamic Data Streams
• Improved Algorithms for Fully Dynamic Maximal Independent Set
• A Tree Structure For Dynamic Facility Location
• Fully dynamic hierarchical diameter k-clustering and k-center
• Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time

Cited by in corpus (1)

• Fully dynamic clustering and diversity maximization in doubling metrics