One and two stage minimum spanning tree problems: average case analysis

Friday, November 5, 2004 - 4:00pm
Skiles 269
Alan Frieze
Carnegie Mellon University

Let the edge weights of a graph G be given independent uniform [0,1] random costs. We review some old results about the expected value of the minimum spanning tree. We then consider a 2-stage problem where independent weights are given for Monday and Tuesday. On Monday we might buy some edges knowing only the distribution of the edge weights for Tuesday and then buy the remaining edges on Tuesday. We present some results on this and on a directed version.