An improved FPTAS for Restricted Shortest Path

被引：85

作者：

Ergun, F

Sinha, R

Zhang, L

机构：

[1] AT& T Labs, Middletown, NJ 07748 USA

[2] Bell Labs, Murray Hill, NJ 07974 USA

[3] Case Western Reserve Univ, Cleveland, OH 44106 USA

来源：

INFORMATION PROCESSING LETTERS | 2002年 / 83卷 / 05期

关键词：

approximation algorithms; combinatorial problems; shortest path; acyclic graphs;

D O I：

10.1016/S0020-0190(02)00205-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：287 / 291

页数：5

共 7 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Goel A, 2001, P INFOCOM

[3] APPROXIMATION SCHEMES FOR THE RESTRICTED SHORTEST-PATH PROBLEM [J].