# Fully Dynamic k-Clustering in tilde O(k) Update Time

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

## Key facts

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

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

- [Competitive strategies to use "warm start" algorithms with predictions](https://mlsanity.com/paper/2405.03661/) (2024)

## Abstract (arXiv)

We present a O(1)-approximate fully dynamic algorithm for the k-median and k-means problems on metric spaces with amortized update time tilde O(k) and worst-case query time tilde O(k2). We complement our theoretical analysis with the first in-depth experimental study for the dynamic k-median problem on general metrics, focusing on comparing our dynamic algorithm to the current state-of-the-art by Henzinger and Kale [ESA'20]. Finally, we also provide a lower bound for dynamic k-median which shows that any O(1)-approximate algorithm with tilde O(poly(k)) query time must have tilde Omega(k) amortized update time, even in the incremental setting.