Back to Search
Start Over
Dynamic Clustering to Minimize the Sum of Radii.
- Source :
-
Algorithmica . Nov2020, Vol. 82 Issue 11, p3183-3194. 12p. - Publication Year :
- 2020
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *OPEN clusters of stars
*DATA structures
*RADIUS (Geometry)
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 82
- Issue :
- 11
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 146495151
- Full Text :
- https://doi.org/10.1007/s00453-020-00721-7