{"ID":2850404,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.21058","arxiv_id":"2510.21058","title":"Hardness of Approximation for Shortest Path with Vector Costs","abstract":"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 \u003c \\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.","short_abstract":"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....","url_abs":"https://arxiv.org/abs/2510.21058","url_pdf":"https://arxiv.org/pdf/2510.21058v1","authors":"[\"Charlie Carlson\",\"Yury Makarychev\",\"Ron Mosenzon\"]","published":"2025-10-24T00:15:09Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}