An improved FPTAS for Restricted Shortest Path

Given a graph with a cost and a delay on each edge, Restricted Shortest Path (RSP) aims to find a min-cost s-t path subject to an end-to-end delay constraint. The problem is NP-hard. In this note we present an FPTAS with an improved running time of O(mn/epsilon) for acyclic graphs, where m and n denote the number of edges and nodes in the graph. Our algorithm uses a scaling and rounding technique similar to that of Hassin {[}Math. Oper. Res. 17 (1) (1992) 36-42]. The novelty of our algorithm lies in its ``adaptivity{''}. During each iteration of our algorithm the approximation parameters are fine-tuned according to the quality of the current solution so that the running time is kept low while progress is guaranteed at each iteration. Our result improves those of Hassin {[}Math. Oper. Res. 17 (1) (1992) 36-42], Phillips {[}Proc. 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 776-785], and Raz and Lorenz {[}Technical Report, 1999]. (C) 2002 Elsevier Science B.V. All rights reserved.