On accuracy of approximation for the resource constrained shortest path problem

The paper we considers the Resource Constrained Shortest Path problem (RCSP). This problem is NP-hard extension of a well-known shortest path problem in the directed graph $G = (V, E)$. In the RCSP problem each arc $e$ from $E$ has a cost $w(e)$ and additional weight functions $r_i(e), i = 1, \dots, k$, which specifying its requirements from a finite set of resource. A polynomial time $\epsilon$-approximation algorithm RevTree based on node labeling method is presented in the paper. The main advantage of the RevTree algorithm over existing ones is its ability to produce $\epsilon$ approximation of the RCSP problem in $\mathcal{O}(\mathopen|V\mathclose|^2)$ time. The present paper provides a proof of complexity and aproximation of RevTree algorithm.