Spring 2005 Seminar Series

DATE: Thursday, March 10, 2005
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
Alan Frieze
Professor of Mathematics
Department of Mathematical Sciences
Carnegie Mellon University

TITLE
One and Two Stage Minimum Spanning Tree Problems: Average Case Analysis

ABSTRACT
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 a directed version.

Joint work with Abie Flaxman and Juan Vera