---
_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 MH, 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. H., &#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 H 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. H. 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 MH, 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.H. 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: 2023-02-16T10:50:51Z
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'
...
---
_id: '11828'
abstract:
- lang: eng
  text: "We consider the problem of dynamically maintaining (approximate) all-pairs
    effective resistances in separable graphs, which are those that admit an n^{c}-separator
    theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations
    of the all-pairs effective resistances of an n-vertex graph G undergoing edge
    insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and
    O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable
    (i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its
    separator can be computed in O~(n) time. Our algorithm is built upon a dynamic
    algorithm for maintaining approximate Schur complement that approximately preserves
    pairwise effective resistances among a set of terminals for separable graphs,
    which might be of independent interest.\r\nWe complement our result by proving
    that for any two fixed vertices s and t, no incremental or decremental algorithm
    can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case
    update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless
    the Online Matrix Vector Multiplication (OMv) conjecture is false.\r\nWe further
    show that for general graphs, no incremental or decremental algorithm can maintain
    the s-t effective resistance problem with worst-case update time O(n^{1-delta})
    and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false."
alternative_title:
- LIPIcs
article_number: '40'
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: Pan
  full_name: Peng, Pan
  last_name: Peng
citation:
  ama: 'Goranci G, Henzinger MH, Peng P. Dynamic effective resistances and approximate
    schur complement on separable graphs. 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.40">10.4230/LIPICS.ESA.2018.40</a>'
  apa: 'Goranci, G., Henzinger, M. H., &#38; Peng, P. (2018). Dynamic effective resistances
    and approximate schur complement on separable graphs. 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.40">https://doi.org/10.4230/LIPICS.ESA.2018.40</a>'
  chicago: Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Dynamic Effective Resistances
    and Approximate Schur Complement on Separable Graphs.” 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.40">https://doi.org/10.4230/LIPICS.ESA.2018.40</a>.
  ieee: G. Goranci, M. H. Henzinger, and P. Peng, “Dynamic effective resistances and
    approximate schur complement on separable graphs,” in <i>26th Annual European
    Symposium on Algorithms</i>, Helsinki, Finland, 2018, vol. 112.
  ista: 'Goranci G, Henzinger MH, Peng P. 2018. Dynamic effective resistances and
    approximate schur complement on separable graphs. 26th Annual European Symposium
    on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112,
    40.'
  mla: Goranci, Gramoz, et al. “Dynamic Effective Resistances and Approximate Schur
    Complement on Separable Graphs.” <i>26th Annual European Symposium on Algorithms</i>,
    vol. 112, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a
    href="https://doi.org/10.4230/LIPICS.ESA.2018.40">10.4230/LIPICS.ESA.2018.40</a>.
  short: G. Goranci, M.H. Henzinger, P. Peng, 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:26:42Z
date_published: 2018-08-14T00:00:00Z
date_updated: 2023-02-16T11:08:08Z
day: '14'
doi: 10.4230/LIPICS.ESA.2018.40
extern: '1'
external_id:
  arxiv:
  - '1802.09111'
intvolume: '       112'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2018.40
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: Dynamic effective resistances and approximate schur complement on separable
  graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2018'
...