---
_id: '11827'
abstract:
- lang: eng
  text: 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.
alternative_title:
- LIPIcs
article_number: '39'
article_processing_charge: No
arxiv: 1
author:
- first_name: 'Gramoz '
  full_name: 'Goranci, Gramoz '
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Dariusz
  full_name: Leniowski, Dariusz
  last_name: Leniowski
citation:
  ama: 'Goranci G, Henzinger M, Leniowski D. A tree structure for dynamic facility
    location. In: <i>26th Annual European Symposium on Algorithms</i>. Vol 112. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2018.39">10.4230/LIPICS.ESA.2018.39</a>'
  apa: 'Goranci, G., Henzinger, M., &#38; Leniowski, D. (2018). A tree structure for
    dynamic facility location. In <i>26th Annual European Symposium on Algorithms</i>
    (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPICS.ESA.2018.39">https://doi.org/10.4230/LIPICS.ESA.2018.39</a>'
  chicago: Goranci, Gramoz , Monika Henzinger, and Dariusz Leniowski. “A Tree Structure
    for Dynamic Facility Location.” In <i>26th Annual European Symposium on Algorithms</i>,
    Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href="https://doi.org/10.4230/LIPICS.ESA.2018.39">https://doi.org/10.4230/LIPICS.ESA.2018.39</a>.
  ieee: G. Goranci, M. Henzinger, and D. Leniowski, “A tree structure for dynamic
    facility location,” in <i>26th Annual European Symposium on Algorithms</i>, Helsinki,
    Finland, 2018, vol. 112.
  ista: 'Goranci G, Henzinger M, Leniowski D. 2018. A tree structure for dynamic facility
    location. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium
    on Algorithms, LIPIcs, vol. 112, 39.'
  mla: Goranci, Gramoz, et al. “A Tree Structure for Dynamic Facility Location.” <i>26th
    Annual European Symposium on Algorithms</i>, vol. 112, 39, Schloss Dagstuhl -
    Leibniz-Zentrum für Informatik, 2018, doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2018.39">10.4230/LIPICS.ESA.2018.39</a>.
  short: G. Goranci, M. Henzinger, D. Leniowski, in:, 26th Annual European Symposium
    on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
conference:
  end_date: 2018-08-22
  location: Helsinki, Finland
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2018-08-20
date_created: 2022-08-12T08:20:57Z
date_published: 2018-08-14T00:00:00Z
date_updated: 2024-11-06T11:57:41Z
day: '14'
doi: 10.4230/LIPICS.ESA.2018.39
extern: '1'
external_id:
  arxiv:
  - '1909.06653'
intvolume: '       112'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2018.39
month: '08'
oa: 1
oa_version: Published Version
publication: 26th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959770811'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A tree structure for dynamic facility location
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2018'
...