@inproceedings{
biabani2024improved,
title={Improved Guarantees for Fully Dynamic \$k\$-Center Clustering with Outliers in General Metric Spaces},
author={Leyla Biabani and Annika Hennes and Denise La Gordt Dillie and Morteza Monemizadeh and Melanie Schmidt},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=OtYCp1yfbX}
}
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+\epsilon)$-approximate 
solution to the $(k,z)$-center clustering problem that covers 
all but at most $(1+\epsilon)z$ points at any time in the sequence with probability $1-k/e^{\Omega(\log k)}$. 
The algorithm achieves an expected amortized update time of $\mathcal{O}(\epsilon^{-2} k^6\log(k) \log(\Delta))$, and is applicable to general metric spaces. 
Our dynamic algorithm presents a significant improvement over the recent dynamic $(14+\epsilon)$-approximation algorithm by Chan, Lattanzi, Sozio, and Wang for this problem.
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