Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time
Abstract
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(k^2)$. 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(\text{poly}(k))$ query time must have $\tilde \Omega(k)$ amortized update time, even in the incremental setting.
Cite
Text
Bhattacharya et al. "Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time." Neural Information Processing Systems, 2023.Markdown
[Bhattacharya et al. "Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/bhattacharya2023neurips-fully/)BibTeX
@inproceedings{bhattacharya2023neurips-fully,
title = {{Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time}},
author = {Bhattacharya, Sayan and Costa, Martín and Lattanzi, Silvio and Parotsidis, Nikos},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/bhattacharya2023neurips-fully/}
}