{"id":"arxiv:2410.17179","kind":"preprint","title":"Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs","authors":["Vikrant Ashvinkumar","Aaron Bernstein","Adam Karczmarz"],"author_count":3,"year":2024,"published":"2024-10-22","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2410.17179","nct_id":null,"source_url":"https://arxiv.org/abs/2410.17179","archive_url":"https://space-kitty.com/papers/arxiv:2410.17179","updated":"2024-10-22","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2410.17179","abstract":"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]$.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}