Improved Approximation Schemes for the Restricted Shortest Path Problem

Abstract

The Restricted Shortest Path (RSP) problem, also known as the Delay-Constrained Least-Cost (DCLC) problem, is an NP-hard bicriteria optimization problem on graphs with $n$ vertices and $m$ edges. In a graph where each edge is assigned a cost and a delay, the goal is to find a min-cost path which does not exceed a delay bound. In this paper, we present improved approximation schemes for RSP on several graph classes. For planar graphs, undirected graphs with positive integer resource (= delay) values, and graphs with $m \in Ω(n \log n)$, we obtain $(1 + \varepsilon)$-approximations in time $O(mn/\varepsilon)$. For general graphs and directed acyclic graphs, we match the results by Xue et al. (2008, [10]) and Ergun et al. (2002, [1]), respectively, but with arguably simpler algorithms.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.