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/

[1] P. Van Mieghem and et al., “Quality of Service Routing”, Quality of Future Internet Services, LNCS, 2856, 2003, 80–117

[2] H.C. Joksch, “The Shortest Route Problem with Constraints”, Mathematical Analysis and Application, 14 (1966), 191–197 | DOI | MR | Zbl

[3] M. Dror, “Note on the complexity of the shortest path models for column generation in VRPTW”, Operation Research, 42 (1994), 977–978 | DOI | Zbl

[4] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, CA, 1979 | MR | Zbl

[5] I. Dumitrescu, N. Boland, “Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem”, Networks, 42 (2003), 135–153 | DOI | MR | Zbl

[6] K. Mehlhorn, M. Ziegelmann, “Resource constrained shortest paths”, Algorithms ESA 2000, LNCS, 1879, 2000, 326–337 | MR | Zbl

[7] M. Jepsen, B. Petersen, S. Spoorendonk, D. Pisinger, “A branch-and-cut algorithm for the capacitated profitable tour problem”, Discrete Optimization, 14 (2014), 78–96 | DOI | MR | Zbl

[8] M. Horvath, T. Kis, “Solving resource constrained shortest path problems with LP-based methods”, Computers, 73 (2016), 150–164 | MR | Zbl

[9] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edn., MIT Press, Boston, 2009 | MR | Zbl

[10] R. Hassin, “Approximation Schemes for the Restricted Shortest Path Problem”, Mathematics Oper. Res., 17 (1992), 36–42 | DOI | MR | Zbl

[11] G. Xue, W. Zhang, J. Tang, K. Thulasiraman, “Polynomial Time Approximation Algorithms for Multi-Constrained QoS Routing”, IEEE/ACM Transactions on Networking, 16:3 (2008), 656–669 | DOI