How does Hassin's algorithm for the Restricted Shortest Path work? I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds $UB$ and $LB$ on $OPT$, so that their ratio is below some constant.

The problem is to find the least-cost path from nodes $1$ to $n$ where the cumulative delay (each edge has a delay/transit time in addition to cost) is no more than some $T$.

For the restricted shortest path problem, the exact solution can be found in pseudopolynomial time $\mathcal{O}(|E|OPT)$like this. 


  Let $g_j(c)$ be the time of the quickest path form node $1$ to node $j$ with cumulative cost $\le c$.
  \begin{align*}
   g_1(c) &amp; =  0,                                                                                            &amp; c = 0,\ldots,OPT, \\
   g_j(0) &amp; =  \infty,                                                                                       &amp; j = 2,\ldots,n, \\
   g_j(c) &amp; =  \min\left\{g_j(c-1), \min_{k \mid c_{kj} \le
   c}\left\{g_k(c-c_{kj}) + t_{kj}\right\}\right\}, &amp; j = 2,\ldots,n; ~ c= 1,\ldots,OPT
\end{align*}


So Hassin constructs a $TEST(k)$ procedure which says $YES$ if $OPT \ge k$ and $NO$ if $OPT &lt; k(1 + \epsilon)$

He then proceeds to pick initial bounds $UB$ and $LB$ and uses the $TEST$ to refine them until $\frac{UB}{LB} = 2$. He then computes the final solution with the exact algorithm, but where each edge cost $c_{ij
}$ is scaled as $\hat{c}_{ij} = \lfloor\frac{c_{ij} (n-1)}{LB\epsilon}\rfloor$. So what I would like to know is how this application of the exact algorithm is actually polynomial. I suppose that the optimal solution in this modified graph is somehow bounded, but I do not see where the ratio of $2$ comes into play.
I have one theory now, which is that the final application of the exact algorithm on the scaled costs has complexity $\mathcal{O}\left(|E| OPT\frac{(n-1)}{LB\epsilon}\right) \subseteq \mathcal{O}(|E| 2LB\frac{(n-1)}{LB\epsilon})=\mathcal{O}(|E| 2\frac{(n-1)}{\epsilon})=\mathcal{O}\left(|E|\frac{n-1}{\epsilon}\right)$ which is then polynomial in $n \le \sqrt{|E|}$ and $\epsilon$. Can anybody confirm this?