Fully Dynamic k-Clustering in Õ(k) Update Time

We present a O(1)-approximate fully dynamic algorithm for the k-median and kmeans problems on metric spaces with amortized update time Õ(k) and worst-case query time Õ(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 [20] . Finally, we also provide a lower bound for dynamic k-median which shows that any O(1)-approximate algorithm with Õ(poly(k)) query time must have Ω(k) amortized update time, even in the incremental setting.