# Approximating the shortest path problem with scenarios

Article · Adam Kasperski, Pawel Zielinski

- Archive id: arxiv:1806.08936
- Published: 2018-06-23
- Venue: Theoretical Computer Science
- DOI: https://doi.org/10.1016/j.tcs.2024.114972
- arXiv: https://arxiv.org/abs/1806.08936
- Citations: 4
- Source URL: https://arxiv.org/abs/1806.08936
- PDF: https://arxiv.org/pdf/1806.08936
- Provenance: arxiv

## 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 $Ω(\\log^{1-ε} K)$ for any $ε\>0$ unless NP$\\subseteq \\text{DTIME}(n^{\\text{polylog} \\,n})$ even for arc series-parallel graphs and within $Ω(\\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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.