Hardness of Approximation for Shortest Path with Vector Costs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917039072870400 |
|---|---|
| author | Carlson, Charlie Makarychev, Yury Mosenzon, Ron |
| author_facet | Carlson, Charlie Makarychev, Yury Mosenzon, Ron |
| contents | We obtain hardness of approximation results for the $\ell_p$-Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer $p \in [2,\infty)$, we show a hardness of $Ω(p(\log n / \log^2\log n)^{1-1/p})$ for both polynomial- and quasi-polynomial-time approximation algorithms. This nearly matches the approximation factor of $O(p(\log n / \log\log n)^{1-1/p})$ achieved by a quasi-polynomial-time algorithm of Makarychev, Ovsiankin, and Tani (ICALP 2025). No hardness of approximation results were previously known for any $p < \infty$. We also present results for the case where $p$ is a function of $n$. For $p = \infty$, we establish a hardness of $\tildeΩ(\log^2 n)$, improving upon the previous $\tildeΩ(\log n)$ hardness result. Our result nearly matches the $O(\log^2 n)$ approximation guarantee of the quasi-polynomial-time algorithm by Li, Xu, and Zhang (ICALP 2025). Finally, we present asymptotic bounds on higher-order Bell numbers, which might be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21058 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hardness of Approximation for Shortest Path with Vector Costs Carlson, Charlie Makarychev, Yury Mosenzon, Ron Data Structures and Algorithms We obtain hardness of approximation results for the $\ell_p$-Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer $p \in [2,\infty)$, we show a hardness of $Ω(p(\log n / \log^2\log n)^{1-1/p})$ for both polynomial- and quasi-polynomial-time approximation algorithms. This nearly matches the approximation factor of $O(p(\log n / \log\log n)^{1-1/p})$ achieved by a quasi-polynomial-time algorithm of Makarychev, Ovsiankin, and Tani (ICALP 2025). No hardness of approximation results were previously known for any $p < \infty$. We also present results for the case where $p$ is a function of $n$. For $p = \infty$, we establish a hardness of $\tildeΩ(\log^2 n)$, improving upon the previous $\tildeΩ(\log n)$ hardness result. Our result nearly matches the $O(\log^2 n)$ approximation guarantee of the quasi-polynomial-time algorithm by Li, Xu, and Zhang (ICALP 2025). Finally, we present asymptotic bounds on higher-order Bell numbers, which might be of independent interest. |
| title | Hardness of Approximation for Shortest Path with Vector Costs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.21058 |