Book ; Online: Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency
2022
Abstract: Thorup [FOCS'01, JACM'04] and Klein [SODA'01] independently showed that there exists a $(1+\epsilon)$-approximate distance oracle for planar graphs with $O(n (\log n)\epsilon^{-1})$ space and $O(\epsilon^{-1})$ query time. While the dependency on $n$ is ... ...
| Abstract | Thorup [FOCS'01, JACM'04] and Klein [SODA'01] independently showed that there exists a $(1+\epsilon)$-approximate distance oracle for planar graphs with $O(n (\log n)\epsilon^{-1})$ space and $O(\epsilon^{-1})$ query time. While the dependency on $n$ is nearly linear, the space-query product of their oracles depend quadratically on $1/\epsilon$. Many follow-up results either improved the space \emph{or} the query time of the oracles while having the same, sometimes worst, dependency on $1/\epsilon$. Kawarabayashi, Sommer, and Thorup [SODA'13] were the first to improve the dependency on $1/\epsilon$ from quadratic to nearly linear (at the cost of $\log^*(n)$ factors). It is plausible to conjecture that the linear dependency on $1/\epsilon$ is optimal: for many known distance-related problems in planar graphs, it was proved that the dependency on $1/\epsilon$ is at least linear. In this work, we disprove this conjecture by reducing the dependency of the space-query product on $1/\epsilon$ from linear all the way down to \emph{subpolynomial} $(1/\epsilon)^{o(1)}$. More precisely, we construct an oracle with $O(n\log(n)(\epsilon^{-o(1)} + \log^*n))$ space and $\log^{2+o(1)}(1/\epsilon)$ query time. Our construction is the culmination of several different ideas developed over the past two decades. Comment: 34 pages, 10 figures |
|---|---|
| Keywords | Computer Science - Data Structures and Algorithms ; F.2.2 |
| Subject code | 005 |
| Publishing date | 2022-07-12 |
| Publishing country | us |
| Document type | Book ; Online |
| Database | BASE - Bielefeld Academic Search Engine (life sciences selection) |
Full text online
More links
Kategorien
Inter-library loan at ZB MED
Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.