*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Please note the talk is at 11 am in 1116 East
Algorithms & Randomness Center (ARC)
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.
