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.