On the random 2-stage minimum spanning tree

ABSTRACT

It is known [7] that if the edge costs of the complete graph Kn are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to ζ(3) = Σ ^∞i=1 i-3. Here we consider the following stochastic two-stage version of this optimization problem. There are two sets of edge costs cM: E ← R and cT: E ← R, called Monday's prices and Tuesday's prices, respectively. For each edge e, both costs cM(e) and cT(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 XM bought on Monday is then completed by the set of edges XT 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 ζ(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 ∈ > 0. We also consider a threshold heuristic, where the algorithm buys on Monday only edges of cost less than α and completes them on Tuesday in an optimal way, and show that the optimal choice for α is α = 1/n with the expected cost ζ(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).

REFERENCES

• 1: D. Aldous, Asymptotics in the random assignment problem, Probability Theory and Related Fields 93 (1992) 507--534.
• 2: David J. Aldous, The ζ (2) limit in the random assignment problem, Random Structures & Algorithms, v.18 n.4, p.381-418, July 2001 [doi>10.1002/rsa.1015]
• 3: A. Beveridge, A. M. Frieze and C. J. H. McDiarmid, Random minimum length spanning trees in regular graphs, Combinatorica 18 (1998) 311--333.
• 4: J. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer, 1997.
• 5: B. Bollobás, Random Graphs, (2nd Edition) Cambridge University Press (2001).
• 6: K. Dhamdere and M. Singh, Handling the random tree, manuscript.
• 7: A. M. Frieze, On the value of a random minimum spanning tree problem, Discrete Applied Mathematics 10 (1985) 47--56.
• 8: G. Lugosi, Concentration-of-measure inequalities, from Workshop on Combinatorics, Probability, and Algorithms at Centre de Reserches Mathématiques, Université de Montréal (2003).
• 9: A. Gupta, private communication.
• 10: S. Janson, T. Luczak, D. E. Knuth and B. G. Pittel, The birth of the giant component, Random Structures and Algorithms 4 (1993) 233--357.
• 11: S. Janson, T. Luczak and A. Ruciński, Random Graphs, John Wiley and Sons (2000).
• 12: S. Linusson and J. Wästlund, A solution of Parisi's conjecture on the random assignment problem, Probability Theory and Related Fields 128 (2004), 419--440.
• 13: Chandra Nair , Balaji Prabhakar , Mayank Sharma, Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.168, October 11-14, 2003