文章基本信息

标题：A Tree Structure For Dynamic Facility Location
本地全文：下载
作者：Gramoz Goranci ; Monika Henzinger ; Dariusz Leniowski 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：112
页码：1-13
DOI：10.4230/LIPIcs.ESA.2018.39
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of clients remains the same, but the metric space can change over time. We show a deterministic algorithm that maintains a constant factor approximation to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion or deletion in metric spaces while answering queries about the cost in O(1) time, where kappa denotes the doubling dimension of the metric. For metric spaces with bounded doubling dimension, the update time is polylogarithmic in the parameters of the problem.
关键词：facility location; dynamic algorithm; approximation; doubling dimension