Stochastic spanning tree problem

AbstractThe 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