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.


1 Answer 1


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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.