article published yes Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 Dariusz Leniowski author Claire Mathieu author 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. Springer Nature2020 eng 0178-4617 1432-0541 1707.0257710.1007/s00453-020-00721-7 82113183-3194 yes Henzinger, Monika, et al. “Dynamic Clustering to Minimize the Sum of Radii.” <i>Algorithmica</i>, vol. 82, no. 11, Springer Nature, 2020, pp. 3183–94, doi:<a href="https://doi.org/10.1007/s00453-020-00721-7">10.1007/s00453-020-00721-7</a>. M. Henzinger, D. Leniowski, C. Mathieu, Algorithmica 82 (2020) 3183–3194. M. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” <i>Algorithmica</i>, vol. 82, no. 11. Springer Nature, pp. 3183–3194, 2020. Henzinger M, Leniowski D, Mathieu C. 2020. Dynamic clustering to minimize the sum of radii. Algorithmica. 82(11), 3183–3194. Henzinger, Monika, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” <i>Algorithmica</i>. Springer Nature, 2020. <a href="https://doi.org/10.1007/s00453-020-00721-7">https://doi.org/10.1007/s00453-020-00721-7</a>. Henzinger, M., Leniowski, D., &#38; Mathieu, C. (2020). Dynamic clustering to minimize the sum of radii. <i>Algorithmica</i>. Springer Nature. <a href="https://doi.org/10.1007/s00453-020-00721-7">https://doi.org/10.1007/s00453-020-00721-7</a> Henzinger M, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. <i>Algorithmica</i>. 2020;82(11):3183-3194. doi:<a href="https://doi.org/10.1007/s00453-020-00721-7">10.1007/s00453-020-00721-7</a> 116742022-07-27T13:58:58Z2024-11-04T11:41:57Z