Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914984156463104 |
|---|---|
| author | Ashvinkumar, Vikrant Bernstein, Aaron Karczmarz, Adam |
| author_facet | Ashvinkumar, Vikrant Bernstein, Aaron Karczmarz, Adam |
| contents | In the restricted shortest paths problem, we are given a graph $G$ whose edges are assigned two non-negative weights: lengths and delays, a source $s$, and a delay threshold $D$. The goal is to find, for each target $t$, the length of the shortest $(s,t)$-path whose total delay is at most $D$. While this problem is known to be NP-hard [Garey and Johnson, 1979] $(1+\varepsilon)$-approximate algorithms running in $\tilde{O}(mn)$ time [Goel et al., INFOCOM'01; Lorenz and Raz, Oper. Res. Lett.'01] given more than twenty years ago have remained the state-of-the-art for directed graphs. An open problem posed by [Bernstein, SODA'12] -- who gave a randomized $m\cdot n^{o(1)}$ time bicriteria $(1+\varepsilon, 1+\varepsilon)$-approximation algorithm for undirected graphs -- asks if there is similarly an $o(mn)$ time approximation scheme for directed graphs.
We show two randomized bicriteria $(1+\varepsilon, 1+\varepsilon)$-approximation algorithms that give an affirmative answer to the problem: one suited to dense graphs, and the other that works better for sparse graphs. On directed graphs with a quasi-polynomial weights aspect ratio, our algorithms run in time $\tilde{O}(n^2)$ and $\tilde{O}(mn^{3/5})$ or better, respectively. More specifically, the algorithm for sparse digraphs runs in time $\tilde{O}(mn^{(3 - α)/5})$ for graphs with $n^{1 + α}$ edges for any real $α\in [0,1/2]$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17179 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs Ashvinkumar, Vikrant Bernstein, Aaron Karczmarz, Adam Data Structures and Algorithms In the restricted shortest paths problem, we are given a graph $G$ whose edges are assigned two non-negative weights: lengths and delays, a source $s$, and a delay threshold $D$. The goal is to find, for each target $t$, the length of the shortest $(s,t)$-path whose total delay is at most $D$. While this problem is known to be NP-hard [Garey and Johnson, 1979] $(1+\varepsilon)$-approximate algorithms running in $\tilde{O}(mn)$ time [Goel et al., INFOCOM'01; Lorenz and Raz, Oper. Res. Lett.'01] given more than twenty years ago have remained the state-of-the-art for directed graphs. An open problem posed by [Bernstein, SODA'12] -- who gave a randomized $m\cdot n^{o(1)}$ time bicriteria $(1+\varepsilon, 1+\varepsilon)$-approximation algorithm for undirected graphs -- asks if there is similarly an $o(mn)$ time approximation scheme for directed graphs. We show two randomized bicriteria $(1+\varepsilon, 1+\varepsilon)$-approximation algorithms that give an affirmative answer to the problem: one suited to dense graphs, and the other that works better for sparse graphs. On directed graphs with a quasi-polynomial weights aspect ratio, our algorithms run in time $\tilde{O}(n^2)$ and $\tilde{O}(mn^{3/5})$ or better, respectively. More specifically, the algorithm for sparse digraphs runs in time $\tilde{O}(mn^{(3 - α)/5})$ for graphs with $n^{1 + α}$ edges for any real $α\in [0,1/2]$. |
| title | Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.17179 |