Improved Guarantees for Fully Dynamic k-Center Clustering with Outliers in General Metric Spaces
Leyla Biabani, Annika Hennes, Denise La Gordt Dillie, Morteza Monemizadeh, Melanie Schmidt
Abstract
The metric k-center clustering problem with z outliers, also known as (k, z)-center clustering, involves clustering a given point set P in a metric space (M, d) using at most k balls, minimizing the maximum ball radius while excluding up to z points from the clustering. This problem holds fundamental significance in various domains, such as machine learning, data mining, and database systems. This paper addresses the fully dynamic version of the problem, where the point set undergoes continuous updates (insertions and deletions) over time. The objective is to maintain an approximate (k, z)-center clustering with efficient update times. We propose a novel fully dynamic algorithm that maintains a (4 + ϵ)-approximate solution to the (k, z)-center clustering problem that covers all but at most (1 + ϵ)z points at any time in the sequence with probability 1 -k/e Ω(log k) . The algorithm achieves an expected amortized update time of O(ϵ -3 k 6 log(k) log(∆)), and is applicable to general metric spaces. Our dynamic algorithm presents a significant improvement over the recent dynamic (14 + ϵ)-approximation algorithm by Chan, Lattanzi, Sozio, and Wang [5] for this problem.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond cites Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
- New Algorithms for Fully-Dynamic k-center with Outliers cites Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
- New Algorithms for Fully-Dynamic k-center with Outliers cites Faster Query Times for Fully Dynamic k-Center Clustering with Outliers
- Faster Query Times for Fully Dynamic k-Center Clustering with Outliers cites Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
Cited by top-tier papers2
Builds on2
- Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious AdversariesMohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger et al.SODA 2023 · 11 citations
- Faster Query Times for Fully Dynamic k-Center Clustering with OutliersLeyla Biabani, Annika Hennes, Morteza Monemizadeh, Melanie SchmidtNeurIPS 2023 · 8 citations
Related papers
- Almost Optimal Fully Dynamic k-Center Clustering with RecourseSayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Silvio Lattanzi et al.ICML 2025
- Fully Dynamic k-Median with Near-Optimal Update Time and RecourseSayan Bhattacharya, Martín Costa, Ermiya FarokhnejadSTOC 2025 · 9 citations
- Fully Dynamic Consistent k-Center ClusteringJakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram et al.SODA 2024 · 5 citations
- Dynamic Consistent k-Center Clustering with Optimal RecourseSebastian Forster, Antonis SkarlatosSODA 2025 · 2 citations
- Fully Dynamic k-Clustering with Fast Update Time and Small RecourseSayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi et al.FOCS 2024 · 1 citation
