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, \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, efficient approximation algorithm.

UDC: 519.2

Received: 14.02.2019
Received in revised form: 20.05.2019
Accepted: 20.08.2019

Language: English

DOI: 10.17516/1997-1397-2019-12-5-621-627

Bibliographic databases:

•