Average-case analysis of combinatorial problems (with emphasis on random spanning trees)

This talk will be a survey of some recent developments in average-case analysis of algorithms for combinatorial problems. I will focus especially on several problems related to finding the minimum spanning tree in a random network. When the cost of the edges between n nodes are selected independently and uniformly from [0,1], the expected cost of the minimum spanning tree converges to a surprising constant [Frieze, Discrete Appl. Math. 1985]. I'll describe some variants of this problem which introduce additional complications and yield other surprising expected values and distributions. In the two-stage stochastic programming version of this problem [Flaxman, Frieze, and Krivelevich, SODA 2005/Random Structures Algorithms 2006], you know the costs of each edge on Monday and the distribution of the costs of each edge on Tuesday. The goal is to select a set of edges to buy on Monday so that when the tree is completed on Tuesday, the expected total cost is minimized. In the bounded-depth minimum spanning tree [Angel, Flaxman, Wilson, Zecchina], the goal is to select a minimum cost set of edges which form a tree of depth at most some given value. Throughout the talk, I will focus on the mutually beneficial interplay between theory and application.

Event Topic

Discrete Applied Math Seminar