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

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2023.

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

- [Dynamic Correlation Clustering in Sublinear Update Time](https://mlsanity.com/paper/2406.09137/) (2024)
- [Label-consistent clustering for evolving data](https://mlsanity.com/paper/2512.15210/) (2025)
- [Dynamic algorithms for k-center on graphs](https://mlsanity.com/paper/2307.15557/) (2023)
- [Adversarially Robust Distributed Count Tracking via Partial Differential Privacy](https://mlsanity.com/paper/2311.00346/) (2023)
- [Clustering with Label Consistency](https://mlsanity.com/paper/2512.19654/) (2025)
- [Is Randomness Necessary for Adaptive Data Analysis?](https://mlsanity.com/paper/2607.07085/) (2026)

## Abstract (arXiv)

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+ε)-approximation in O(k · 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(k2· polylog(n,Delta)), and is due to Chan, Gourqin, and Sozio (2018). Moreover, we demonstrate that our runtime is optimal up to 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(n k) 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.