Algorithms & Randomness Center (ARC)

Alan Frieze – Carnegie Mellon University

Wednesday, September 23, 2015

Klaus 1116 E - 11:00 am

(Refreshments will be served in Klaus 2222 at Noon)

 Title:

Title: Probabilistic analysis of some combinatorial optimization problems.

Abstract:

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.