---
res:
bibo_abstract:
- 'We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest
paths problem in unweighted undirected n-node m-edge graphs under edge deletions.
The fastest algorithm for this problem is a randomized algorithm with a total
update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004).
The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach
(JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We
improve these results as follows: (1) We present an algorithm with a total update
time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in
addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time
when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in
the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial
algorithm with 1 + ϵ multiplicative error cannot have an additive error less than
2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor,
Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska
Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 +
ϵ)-approximation algorithm (without an additive error) with the same time guarantees,
improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n))
) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation
and time guarantees. (2) We present a deterministic algorithm with a total update
time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative
error of 1 + ϵ and gives the first improved deterministic algorithm since 1981.
It also answers an open question raised by Bernstein in his STOC 2013 paper. In
order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach
tree algorithm which maintains a bounded-distance shortest-paths tree on a certain
type of emulator called locally persevering emulator. (2) A derandomization technique
based on moving Even-Shiloach trees as a way to derandomize the standard random
set argument. These techniques might be of independent interest.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
- foaf_Person:
foaf_givenName: Sebastian
foaf_name: Krinninger, Sebastian
foaf_surname: Krinninger
- foaf_Person:
foaf_givenName: Danupon
foaf_name: Nanongkai, Danupon
foaf_surname: Nanongkai
bibo_doi: 10.1109/focs.2013.64
dct_date: 2013^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0272-5428
dct_language: eng
dct_publisher: Institute of Electrical and Electronics Engineers@
dct_title: 'Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier
and derandomization@'
...