Confidence regional method of stochastic spanning tree problem

The authors consider a P model version of stochastic spanning tree problems with random edge costs. Parameters of underling probability distribution of edge costs are unknown, and so they are estimated by a confidence region from statistical data. The problem is first transformed into a deterministic equivalent problem with a minimax type objective function and a confidence region of means and variances, since the authors assume normal distributions with respect to random edge costs. The present model reflects the situation that the maximum possible damage due to an unknown parameter should be minimized. The authors show the problem can be reduced to the deterministic equivalent problem of another stochastic spanning tree problem, which is already investigated by them. Thus, they can find an optimal spanning tree of the original problem very efficiently by this reduction.