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

Mohammad Hossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

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(k2 · 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 (Equation presented) approximation in O(k·polylog(n, ∆)) amortized update time. Further, we demonstrate that any algorithm which achieves a (Equation presented)-approximation against adaptive adversaries requires f(k, n) update time, for any arbitrary function f. Thus, in the regime where k(Equation presented), we close the complexity of the problem up to polylog(n, ∆) factors in the update time. Our lower bound extends to other k-clustering tasks in arbitrary metric spaces, including k-medians and k-means. Finally, despite the aforementioned lower bounds, we demonstrate that an update time sublinear in k is possible against oblivious adversaries for metric spaces which admit locally sensitive hash functions (LSH), resulting in improved algorithms for a large class of metrics including Euclidean space, lp-spaces, the Hamming Metric, and the Jaccard Metric. We also give the first fully dynamic O(1)-approximation algorithms for the closely related k-sum-of-radii and k-sum-of-diameter problems, with O(poly(k, log ∆)) update time.

Original languageEnglish
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages2677-2727
Number of pages51
ISBN (Electronic)9781611977554
StatePublished - 2023
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: 22 Jan 202325 Jan 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period22/01/2325/01/23

Fingerprint

Dive into the research topics of 'Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries'. Together they form a unique fingerprint.

Cite this