Simple Efficient Approximation Scheme for the Restricted Shortest Path Problem

In this short paper we give a very simple fully polynomial approximation scheme for the restricted shortest path problem. The complexity of this epsilon-approximation scheme is O(|E| n (loglog n + 1/epsilon)), which improves Hassins original [Has92] by a factor of n and is compared favorably with the much more complex result of Cynthia Phillips [Phil93]. Furthermore, this complexity bound is valid for any graph regardless of the cost values. Our algorithm is based on Hassins original result with two improvements. First we modify Hassins result and achieve time complexity of O(|E| n (loglog (UB/LB) + 1/epsilon)), where UB and LB are upper and lower bounds for the problem. This modified version can be applied to general graphs with any cost values. Then we combine it with our second contribution, which shows how to find an upper and a lower bound such that UB/LB n, to obtain the claimed result.