Journal of Siberian Federal University. Mathematics & Physics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



J. Sib. Fed. Univ. Math. Phys.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


J. Sib. Fed. Univ. Math. Phys., 2019, Volume 12, Issue 5, Pages 621–627 (Mi jsfu798)  

On accuracy of approximation for the resource constrained shortest path problem

Aleksandr A. Soldatenko

Institute of Mathematics and Computer Science, Siberian Federal University, Svobodny, 79, Krasnoyarsk, 660041, Russia

Abstract: 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, …, 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, efficient approximation algorithm.

DOI: https://doi.org/10.17516/1997-1397-2019-12-5-621-627

Full text: PDF file (102 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.2
Received: 14.02.2019
Received in revised form: 20.05.2019
Accepted: 20.08.2019
Language:

Citation: Aleksandr A. Soldatenko, “On accuracy of approximation for the resource constrained shortest path problem”, J. Sib. Fed. Univ. Math. Phys., 12:5 (2019), 621–627

Citation in format AMSBIB
\Bibitem{Sol19}
\by Aleksandr~A.~Soldatenko
\paper On accuracy of approximation for the resource constrained shortest path problem
\jour J. Sib. Fed. Univ. Math. Phys.
\yr 2019
\vol 12
\issue 5
\pages 621--627
\mathnet{http://mi.mathnet.ru/jsfu798}
\crossref{https://doi.org/10.17516/1997-1397-2019-12-5-621-627}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000501589200011}


Linking options:
  • http://mi.mathnet.ru/eng/jsfu798
  • http://mi.mathnet.ru/eng/jsfu/v12/i5/p621

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Журнал Сибирского федерального университета. Серия "Математика и физика"
    Number of views:
    This page:63
    Full text:15
    References:6

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021