.png){kind=icon}
返回
On the robust shortest path problem
.png){kind=icon}
PRE
AI
DOI：10.1016/S0305-0548(97)00085-3.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The shortest path (SP) problem in a network with nonnegative are lengths can be solved easily by Dijkstra's labeling algorithm in polynomial time. In the case of significant uncertainty of the are lengths, a robustness approach is more appropriate. In this paper, we study the SP problem under are length uncertainties. A scenario approach is adopted to characterize uncertainties. Two robustness criteria are specified: the absolute robust criterion and the robust deviation criterion. We show that under both criteria the robust SP problem is NP-complete even for the much more restricted layered networks of width 2, and with only 2 scenarios. A pseudo-polynomial algorithm is devised to solve the robust SP problem in general networks under bounded number of scenarios. Also presented is a more efficient algorithm for layered networks. However, in the case of unlimited number of scenarios, we show that the robust SP problem is strongly NP-hard. A simple heuristic for finding a good robust shortest path is provided, and the worst case performance is analyzed. (C) 1998 Elsevier Science Ltd. All rights reserved.
Keyword:
DECISIONS
SETS
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
暂无机构信息
引用论文
Vinblastine and Interferon-Gamma Combination with and without 13-Cis Retinoic Acid for Patients with Advanced Renal Cell Carcinoma.png)
Oncology
OncologyIF0
PREAI
分享收藏On the Prediction of Mechanical Behavior of Particulate Composites Using an Improved Modulus Degradation Model基于改进的模量退化模型对颗粒复合材料的力学行为进行预测
PREAI
分享收藏 没有更多内容
没有更多内容