.png){kind=icon}
返回
Improved polynomial algorithms for robust bottleneck problems with interval data
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2009.03.013.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
To model uncertainties in a problem one can provide intervals of uncertainty specifying a range for each uncertain parameter value. To hedge against 'worst-case scenarios', i.e., most unwelcome realizations of the uncertain parameters after a solution has been determined, the minmax-regret criterion has been adopted in robust optimization. Within this field, we consider bottleneck problems with one or more uncertain parameter functions. We apply a known polynomial time solution scheme for a number of specific problems of this type with one uncertain parameter function. This leads to improved algorithms of reduced complexity, e.g., for the bottleneck Steiner tree problem and the bottleneck assignment problem. Further, we formulate a framework to solve single machine scheduling problems in polynomial time under the maximum tardiness criterion, with up to three uncertain parameter functions. (C) 2009 Elsevier Ltd. All rights reserved.
Keyword:
Minmax regret
Bottleneck criterion
Interval data
Sequencing
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
Effects of Group Counseling Transmitted Through Videoconferencing on Changes in Eating Behaviors
.png){kind=icon}
PREAI
分享收藏
The computational complexity of the relative robust shortest path problem with interval data区间数据相对鲁棒最短路径问题的计算复杂性
PREAI
分享收藏分享收藏
查看更多内容