Back to Search
Start Over
Approximating the shortest path problem with scenarios
- Publication Year :
- 2018
-
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 $\Omega(\log^{1-\epsilon} K)$ for any $\epsilon>0$ unless NP$\subseteq \text{DTIME}(n^{\text{polylog} \,n})$ even for arc series-parallel graphs and within $\Omega(\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 $\widetilde{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.
- Subjects :
- Computer Science - Data Structures and Algorithms
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1806.08936
- Document Type :
- Working Paper