Stochastic spanning tree problem |
| |
Authors: | Hiroaki Ishii Shōgo Shiode Toshio Nishida Yoshikazu Namasuya |
| |
Institution: | Department of Applied Physics, Faculty of Engineering, Osaka University, Osaka, Japan;Murata Manufacturing Company Limited, Kyoto, Japan |
| |
Abstract: | The minimal spanning tree problem has been well studied and until now many efficient algorithms such as 5,6] have been proposed. This paper generalizes it toward a stochastic version, i.e., considers a stochastic spanning tree problem in which edge costs are not constant but random variables and its objective is to find an optimal spanning tree satisfying a certain chance constraint. This problem may be considered as a discrete version of P-model first introduced by Kataoka 4].First it is transformed into its deterministic equivalent problem P. Then, an auxiliary problem P(R) with a positive parameter R is defined. After clarifying close relations between P and P(R), this paper proposes a polynomial order algorithm fully utilizing P(R). Finally, more improvement of the algorithm and applicability of this type algorithm to other discrete stochastic programming problems are discussed. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|