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) & = 0, & c = 0,\ldots,OPT, \\ g_j(0) & = \infty, & j = 2,\ldots,n, \\ g_j(c) & = \min\left\{g_j(c-1), \min_{k \mid c_{kj} \le c}\left\{g_k(c-c_{kj}) + t_{kj}\right\}\right\}, & 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 < 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.
