On accuracy of approximation for the resource constrained shortest path problem

Рассматривается NP-трудная задача поиска ресурсоограниченного кратчайшего пути, известная под названием Resource Constrained Shortest Path (RCSP). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе $G = (V, E)$, когда для каждой дуги $e \in E$ кроме основной весовой функции $w(e)$ дополнительно задаются функции $r_i(e), i = 1, \dots, k$, численно отражающие потребности в ресурсах, которые необходимы для передвижения по этой дуге. Предлагается полиномиальный $\epsilon$-приближенный алгоритм RevTree, использующий специальную маркировку вершин. Основное преимущество алгоритма RevTree по сравнению с существующими алгоритмами: он быстро находит допустимое решение задачи за $\mathcal{O}(\mathopen|V\mathclose|^2)$ время, отклоняясь от оптимального решения на величину, не превышающую $\epsilon$. В работе приведены доказательства оценок сложности и точности алгоритма RevTree.