ARC/ACO Colloquium: Alan Frieze - Carnegie Mellon University

Event Details

Dani Denton
denton at cc dot gatech dot edu


Summary Sentence: Klaus 1116 East at 11 am (Note: different day, time and location)

Full Summary: No summary paragraph submitted.

Please note the talk is at 11 am in 1116 East

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: Probabilistic analysis of some combinatorial optimization problems.


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.



Related Links

Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Algorithm and Randomness Center, ARC, Computational Complexity, Computational Learning Theory, Georgia Tech, Probabilistic Combinatorics, Theoretical Computer Science and Operations Research
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Sep 4, 2015 - 1:37pm
  • Last Updated: Apr 13, 2017 - 5:18pm