文章基本信息

标题：Dynamic Clustering to Minimize the Sum of Radii
本地全文：下载
作者：Monika Henzinger ; Dariusz Leniowski ; Claire Mathieu 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：48:1-48:10
DOI：10.4230/LIPIcs.ESA.2017.48
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：dynamic algorithm; clustering; approximation; doubling dimension