CHANCE-CONSTRAINED BOTTLENECK SPANNING TREE PROBLEM

被引：3

作者：

ISHII, H ^{[1
]}

SHIODE, S ^{[1
]}

机构：

[1] OSAKA UNIV,FAC ENGN,OSAKA 565,JAPAN

来源：

ANNALS OF OPERATIONS RESEARCH | 1995年 / 56卷

关键词：

D O I：

10.1007/BF02031706

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we consider a stochastic version of the bottleneck spanning tree in which edge costs are independent random variables. Our problem is to find an optimal spanning tree and optimal satisficing level of the chance constraint with respect to the bottleneck (maximum cost) edge of the spanning tree. The problem is first transformed into a deterministic equivalent problem. Then a subproblem in order to solve the problem is introduced and the close relation between these problems is clarified. Finally, based on the relation, polynomial time solution procedures to solve the problem are proposed under two special functions of satisficing level which are given as examples to be solved easily.

引用

页码：177 / 187

页数：11