一类双约束最短路问题的近似算法

被引：1

作者：

于立勇

李曙光

机构：

[1] 山东大学数学与系统科学学院

[2] 山东大学数学与系统科学学院济南

[3] 济南

来源：

关键词：

最短路问题; 约束; 动态规划; 全多项时间近似方案;

D O I：

暂无

中图分类号：

O221 [规划论（数学规划）];

学科分类号：

070105 ; 1201 ;

摘要：

带时间和边数约束的双约束最短路问题是NP 完备的 .它的一种拟多项式精确算法可以利用动态规划方法给出 ,在此基础上采用rounding和scaling的处理技术得到了一种全多项式时间近似方案 (FPAS) .

引用

页码：304 / 306+311 +311

页数：4

共 5 条

[1]

Combinatorial Optimization: Algorithms and Complexity. C H Papadimitriou,K Steiglitz. . 1982

[2]

Approximation of Pareto Optima in Multipleobjective Shortest Path Problems. Arthur Warburton. Operations Research . 1987

[3]

计算机和难解性[M]. 科学出版社[美]加里(Garey,M·R·)[美]约翰逊(Johnson,D·S·) 著, 1987

[4]

General Techniques for Combinatorial Approximation. Sartag Sahni. Operations Research . 1977

[5]

Approximation Schemes for the Resticted Shortest Path Problem. Refael Hassin. Mathematics of Operations Research . 1992