Geodesic
On accuracy of approximation for the resource constrained shortest path problem
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 12 (2019) no. 5, pp. 621-627

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: combinatorial optimization, resource constrained shortest path, graph-based algorithm
Mots-clés : efficient approximation algorithm. 
@article{JSFU_2019_12_5_a10,
     author = {Aleksandr A. Soldatenko},
     title = {On accuracy of approximation for the resource constrained shortest path problem},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {621--627},
     publisher = {mathdoc},
     volume = {12},
     number = {5},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2019_12_5_a10/}
}
TY  - JOUR
AU  - Aleksandr A. Soldatenko
TI  - On accuracy of approximation for the resource constrained shortest path problem
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2019
SP  - 621
EP  - 627
VL  - 12
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2019_12_5_a10/
LA  - en
ID  - JSFU_2019_12_5_a10
ER  - 
%0 Journal Article
%A Aleksandr A. Soldatenko
%T On accuracy of approximation for the resource constrained shortest path problem
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2019
%P 621-627
%V 12
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2019_12_5_a10/
%G en
%F JSFU_2019_12_5_a10
Aleksandr A. Soldatenko. On accuracy of approximation for the resource constrained shortest path problem. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 12 (2019) no. 5, pp. 621-627. http://geodesic.mathdoc.fr/item/JSFU_2019_12_5_a10/