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.)

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
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1707.02577

Search this title in

Google Scholar