On Two-Stage Stochastic Minimum Spanning Trees

We consider the undirected minimum spanning tree problem in a stochastic optimization setting. For the two-stage stochastic optimization formulation with finite scenarios, a simple iterative randomized rounding method on a natural LP formulation of the problem yields a nearly best-possible approximation algorithm. We then consider the Stochastic minimum spanning tree problem in a more general black-box model and show that even under the assumptions of bounded inflation the problem remains log n-hard to approximate unless P = NP; where n is the size of graph. We also give approximation algorithm matching the lower bound up to a constant factor. Finally, we consider a slightly different cost model where the second stage costs are independent random variables uniformly distributed between [0, 1]. We show that a simple thresholding heuristic has cost bounded by the optimal cost plus ζ(3) 4 + o(1).