Back to Search
Start Over
Fully Dynamic k-Center Clustering with Outliers.
- Source :
-
Algorithmica . Jan2024, Vol. 86 Issue 1, p171-193. 23p. - Publication Year :
- 2024
-
Abstract
- 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. We also complement our positive result with a lower bound showing that any constant (non bi-criteria) approximation algorithm has amortized cost at least linear in z. Finally, we conduct an in-depth experimental analysis of our algorithm on Twitter, Flickr, and Air-Quality datasets showing the effectiveness of our approach. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*DYNAMIC models
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 86
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 174581689
- Full Text :
- https://doi.org/10.1007/s00453-023-01159-3