Hardness of Approximation for Shortest Path with Vector Costs

Charlie Carlson, Yury Makarychev, Ron Mosenzon

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,\i…