@inproceedings{11827,
  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.},
  author       = {Goranci, Gramoz  and Henzinger, Monika H and Leniowski, Dariusz},
  booktitle    = {26th Annual European Symposium on Algorithms},
  isbn         = {9783959770811},
  issn         = {1868-8969},
  location     = {Helsinki, Finland},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{A tree structure for dynamic facility location}},
  doi          = {10.4230/LIPICS.ESA.2018.39},
  volume       = {112},
  year         = {2018},
}

@inproceedings{11828,
  abstract     = {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.
We 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.
We 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.},
  author       = {Goranci, Gramoz and Henzinger, Monika H and Peng, Pan},
  booktitle    = {26th Annual European Symposium on Algorithms},
  isbn         = {9783959770811},
  issn         = {1868-8969},
  location     = {Helsinki, Finland},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Dynamic effective resistances and approximate schur complement on separable graphs}},
  doi          = {10.4230/LIPICS.ESA.2018.40},
  volume       = {112},
  year         = {2018},
}