Improved approximation schemes for the restricted shortest path problem

Abstract

In this thesis we present several variants of an approximation scheme for the restricted shortest path problem. This problem concerns finding a shortest path with respect to one criterion while not exceeding a length bound with respect to another criterion. After formally introducing the problem, we describe the approximation scheme by Lorenz and Raz. Our algorithm then introduces additional steps to reduce the runtime complexity from O(|E|n(1/epsilon + log log n)) to O(|E|n(1/epsilon + \log \log \log n)). A variant of this algorithm yields a complexity of O(|E|n(1/epsilon + (n log n) / m)), which is a further improvement for sufficiently dense graphs. Furthermore, a slight modification leads to an O(|E|n(1/epsilon + 1))-algorithm for directed acyclic graphs, providing an arguably easier algorithm than the algorithm proposed by Ergun et al.