On the random 2-stage minimum spanning tree

It is known [A. M. Frieze, Discrete App] Math 10 (1985), 47-56] that if the edge costs of the complete graph K,, are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to zeta(3) = Sigma(infinity)(i=1) i(-3). Here we consider the following stochastic two-stage version of this optimization problem. There are two sets of edge costs c(M): E -> R and c(T): E -> R, called Monday's prices and Tuesday's prices, respectively. For each edge e, both costs c(M)(e) and C-T(e) are independent random variables, uniformly distributed in [0, 1]. The Monday costs are revealed first. The algorithm has to decide on Monday for each edge e whether to buy it at Monday's price cm(e), or to wait until its Tuesday price CT(e) appears. The set of edges X-M bought on Monday is then completed by the set of edges X-T bought on Tuesday to form a spanning tree. If both Monday's and Tuesday's prices were revealed simultaneously, then the optimal solution would have expected cost zeta(3)/2 + o(1). We show that, in the case of two-stage optimization, the expected value of the optimal cost exceeds (3)/2 by an absolute constant epsilon > 0. We also consider a threshold heuristic, where the algorithm buys on Monday only edges of cost less than alpha and completes them on Tuesday in an optimal way, and show that the optimal choice for alpha is alpha = 1/n with the expected cost zeta(3) - 1/2 + o(1). The threshold heuristic is shown to be sub-optimal. Finally we discuss the directed version of the problem, where the task is to construct a spanning out-arborescence rooted at a fixed vertex r, and show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value 1 - 1/e + o(1). (c) 2005 Wiley Periodicals, Inc.