Approximating the Distribution Function of Minimum Spanning Tree Cost with Normally Disributed Stochastic Edge Weights

摘要

Given a graph G of n vertices whose edge weights are random variables and obey mutually independent normal distributions, we consider a stochastic minimum spanning tree problem. The weight of the minimum spanning tree is also a random variable, but its distribution function F{sub}(MST)(x) cannot be represented by a simple distribution function in general. We show an algorithm, whose output is a approximation function F{top}～(x) of the distribution function of stochastic minimum spanning tree weight. Its running time is O(MST(G) + m + n log n), where m is the number of edges in G and MST(G) is the time complexity of the (deterministic) minimum spanning tree weights. Let T be the family of all spanning trees in G. F{top}～(x) gives an upper bound on F{sub}(MST)(x) for x such that F{top}～(x) ≤ 1-2{sup}(-|T|)|, and F{top}～{x} satisfies that |(F{sub}(MST)){sup}(-1)(a) - (F{top}～){sup}(-1)(a)|=o(nσ(log n){sup}(1/2)) for 0 < a ≤ 1-2{sup}(-|T|) where σ{sup}2 is the maximum variance of edge weights.