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

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, ∆)) amortized update time. Here, n is an upper bound on the number of active points at any time, and ∆ is the aspect ratio of the metric space. Previously, the best known amortized update time was O(k 2 • polylog(n, ∆)), and is due to Chan, Gourqin, and Sozio (2018). Moreover, we demonstrate that our runtime is optimal up to polylog(n, ∆) 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 Ω(nk) distance queries to achieve any non-trivial approximation factor. This implies a lower bound of Ω(k) which holds even for the insertions-only setting.

For adaptive adversaries, we give the first deterministic algorithm for fully dynamic k-center which achieves a O min log(n/k) log log n , k approximation in O(k • polylog(n, ∆)) amortized update time. Further, we demonstrate that any algorithm which achieves a O min log n k log f (k,2n) , kapproximation against adaptive adversaries requires f (k, n) update time, for any arbitrary func-