Probabilistic analysis of some combinatorial optimization problems

Joint ACO and ARC Colloquium
Wednesday, September 23, 2015 - 11:05am for 1 hour (actually 50 minutes)
Klaus 1116 E
Alan Frieze – Carnegie Mellon University
Robin Thomas
We consider the following probabilistic model. The edges of a (complete) graph have unknown random edge weights. We want to build a minimum cost structure. We can ask for the weight of an edge and then accept or reject the edge. Once rejected, the edge cannot be accepted later. We must accept enough edges to support a structure and we are charged for all the edges accepted, even if not used. We give results in this model for minimum spanning tree, perfect matching and shortest path. Joint work with Colin Cooper and Wesley Pegden.