Dynamic clustering to minimize the sum of radii
Henzinger MH, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize the sum of radii. Algorithmica. 82(11), 3183–3194.
Download (ext.)
https://doi.org/10.48550/arXiv.1707.02577
[Preprint]
Journal Article
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Leniowski, Dariusz;
Mathieu, Claire
Corresponding author has ISTA affiliation
Abstract
In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem.
Publishing Year
Date Published
2020-11-01
Journal Title
Algorithmica
Publisher
Springer Nature
Volume
82
Issue
11
Page
3183-3194
ISSN
eISSN
IST-REx-ID
Cite this
Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. Algorithmica. 2020;82(11):3183-3194. doi:10.1007/s00453-020-00721-7
Henzinger, M. H., Leniowski, D., & Mathieu, C. (2020). Dynamic clustering to minimize the sum of radii. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-020-00721-7
Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” Algorithmica. Springer Nature, 2020. https://doi.org/10.1007/s00453-020-00721-7.
M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” Algorithmica, vol. 82, no. 11. Springer Nature, pp. 3183–3194, 2020.
Henzinger MH, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize the sum of radii. Algorithmica. 82(11), 3183–3194.
Henzinger, Monika H., et al. “Dynamic Clustering to Minimize the Sum of Radii.” Algorithmica, vol. 82, no. 11, Springer Nature, 2020, pp. 3183–94, doi:10.1007/s00453-020-00721-7.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1707.02577