This paper is not yet publicly available. If you want a copy please email me .

Abstract:

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 ( \log \log n + 1/\epsilon))$, which improves Hassin's original result \cite{Has92} by a factor of $n$ and is compared favoritly with the much more complex result of Cynthia Phillips \cite{Phil93}. Furthermore, this complexity bound is valid for any graph regardless of the cost values. Our algorithm is based on Hassin's original result \cite{Has92} with two improvements. First we modify Hassin's result and achieve time complexity of $O(|E| n ( \log \log (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 \leq n$, to obtain the claimed result.