2026-07-23T16:35:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7874 2024-03-06T10:41:21Z ddc:004 open_access

Dynamic Clustering to Minimize the Sum of Radii Henzinger, Monika Leniowski, Dariusz Mathieu, Claire dynamic algorithm clustering approximation doubling dimension 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Monika Henzinger and Dariusz Leniowski and Claire Mathieu 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.48 urn:nbn:de:0030-drops-78749 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.48 eng https://creativecommons.org/licenses/by/3.0/legalcode