Approximating the shortest path problem with scenarios

Abstract

This paper discusses the shortest path problem in a general directed graph with $n$ nodes and $K$ cost scenarios (objectives). In order to choose a solution, the min-max criterion is applied. The min-max version of the problem is hard to approximate within $\hat{I}\text{c◯}({\log }^{1-\hat{I}\mu }K)$ for any $\hat{I}\mu >0$ unless NP$\subseteq \text{DTIME}(n^{\text{polylog}n})$ even for arc series-parallel graphs and within $\hat{I}\text{c◯}(\log n/\log \log n)$ unless NP$\subseteq \text{ZPTIME}(n^{\log \log n})$ for acyclic graphs. The best approximation algorithm for the min-max shortest path problem in general graphs, known to date, has an approximation ratio of~$K$. In this paper, an $\tilde{O}(\sqrt{n})$ flow LP-based approximation algorithm for min-max shortest path in general graphs is constructed. It is also shown that the approximation ratio obtained is close to an integrality gap of the corresponding flow LP relaxation.