License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.39
URN: urn:nbn:de:0030-drops-95026
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9502/
Go to the corresponding LIPIcs Volume Portal

Goranci, Gramoz ; Henzinger, Monika ; Leniowski, Dariusz

A Tree Structure For Dynamic Facility Location

pdf-format:
LIPIcs-ESA-2018-39.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{goranci_et_al:LIPIcs:2018:9502,
  author =	{Gramoz Goranci and Monika Henzinger and Dariusz Leniowski},
  title =	{{A Tree Structure For Dynamic Facility Location}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{39:1--39:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9502},
  URN =		{urn:nbn:de:0030-drops-95026},
  doi =		{10.4230/LIPIcs.ESA.2018.39},
  annote =	{Keywords: facility location, dynamic algorithm, approximation, doubling dimension}
}

Keywords: facility location, dynamic algorithm, approximation, doubling dimension
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI