English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We study dynamic $(1+\epsilon)$-approximation algorithms for the all-pairsshortest paths problem in unweighted undirected $n$-node $m$-edge graphs underedge deletions. The fastest algorithm for this problem is a randomizedalgorithm with a total update time of $\tilde O(mn/\epsilon)$ and constantquery time by Roditty and Zwick [FOCS 2004]. The fastest deterministicalgorithm is from a 1981 paper by Even and Shiloach [JACM 1981]; it has a totalupdate time of $O(mn^2)$ and constant query time. We improve these results asfollows: (1) We present an algorithm with a total update time of $\tildeO(n^{5/2}/\epsilon)$ and constant query time that has an additive error of $2$in addition to the $1+\epsilon$ multiplicative error. This beats the previous$\tilde O(mn/\epsilon)$ time when $m=\Omega(n^{3/2})$. Note that the additiveerror is unavoidable since, even in the static case, an $O(n^{3-\delta})$-time(a so-called truly subcubic) combinatorial algorithm with $1+\epsilon$multiplicative error cannot have an additive error less than $2-\epsilon$,unless we make a major breakthrough for Boolean matrix multiplication [Dor etal. FOCS 1996] and many other long-standing problems [Vassilevska Williams andWilliams FOCS 2010]. The algorithm can also be turned into a$(2+\epsilon)$-approximation algorithm (without an additive error) with thesame time guarantees, improving the recent $(3+\epsilon)$-approximationalgorithm with $\tilde O(n^{5/2+O(\sqrt{\log{(1/\epsilon)}/\log n})})$ runningtime of Bernstein and Roditty [SODA 2011] in terms of both approximation andtime guarantees. (2) We present a deterministic algorithm with a total updatetime of $\tilde O(mn/\epsilon)$ and a query time of $O(\log\log n)$. Thealgorithm has a multiplicative error of $1+\epsilon$ and gives the firstimproved deterministic algorithm since 1981. It also answers an open questionraised by Bernstein [STOC 2013].

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization