TY - GEN
T1 - Fully Dynamic k-Center Clustering with Outliers
AU - Chan, T. H.Hubert
AU - Lattanzi, Silvio
AU - Sozio, Mauro
AU - Wang, Bo
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022/1/1
Y1 - 2022/1/1
N2 - We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a “small” amortized cost, i.e. a “small” number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input.
AB - We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a “small” amortized cost, i.e. a “small” number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input.
KW - Approximation algorithm
KW - Clustering
KW - Fully dynamic
UR - https://www.scopus.com/pages/publications/85148014661
U2 - 10.1007/978-3-031-22105-7_14
DO - 10.1007/978-3-031-22105-7_14
M3 - Conference contribution
AN - SCOPUS:85148014661
SN - 9783031221040
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 150
EP - 161
BT - Computing and Combinatorics - 28th International Conference, COCOON 2022, Proceedings
A2 - Zhang, Yong
A2 - Miao, Dongjing
A2 - Möhring, Rolf
PB - Springer Science and Business Media Deutschland GmbH
T2 - 28th International Conference on Computing and Combinatorics, COCOON 2022
Y2 - 22 October 2022 through 24 October 2022
ER -