Name
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 thisdynamic sum-of-radii clusteringproblem. 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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s00453-020-00721-7 | ALGORITHMICA |
Keywords | DocType | Volume |
Dynamic algorithm, Clustering in metric space, Approximation, Doubling dimension | Journal | 82 |
Issue | ISSN | Citations |
11 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Monika Rauch Henzinger | 1 | 4307 | 481.86 |
| Dariusz Leniowski | 2 | 22 | 3.07 |
| Claire Mathieu | 3 | 6 | 2.78 |