How does Hassin's algorithm for the Restricted Shortest Path work?
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?