On Accuracy of Approximation for the Resource Constrained Shortest Path Problem

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 ri(e); i = 1; : : : ; k, which specifying its requirements from a finite set of resource. A polynomial time ϵ-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 ϵ approximation of the RCSP problem in O(jV j2) time. The present paper provides a proof of complexity and aproximation of RevTree algorithm

Рассматривается NP-трудная задача поиска ресурсоограниченного кратчайшего пути, известная под названием Resource Constrained Shortest Path (RCSP). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе G = (V;E), когда для каждой дуги e 2 E кроме основной весовой функции w(e) дополнительно задаются функции ri(e); i = 1; : : : ; k, числен- но отражающие потребности в ресурсах, которые необходимы для передвижения по этой дуге. Предлагается полиномиальный ϵ-приближенный алгоритм RevTree, использующий специальную маркировку вершин. Основное преимущество алгоритма RevTree по сравнению с существующими алгоритмами: он быстро находит допустимое решение задачи за O(jV j2) время, отклоняясь от оптимального решения на величину, не превышающую ϵ. В работе приведены доказательства оценок сложности и точности алгоритма RevTree