[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

~REMINDER~

THEORY SEMINAR
Date:         Tuesday, October 16,  2012
Time:        3 p.m.
Place:        Ryerson 251, 1100 E. 58th Street
_________________________ 


Speaker:    Yuri Makarychev
From:        Toyota Technological Institute at Chicago (TTIC)
Title: 	Approximation Algorithms for Semi-random Graph Partitioning Problems
Abstract:  Many combinatorial optimization problems are much simpler in practice than in the worst-case. One of the challenges in the area of approximation algorithms is to explain this phenomenon and to design algorithms that work well in real-life. In this talk, we will discuss one of the models of real-life instances -- the semi-random model, which was originally introduced by Blum and Spencer for the k coloring problem.  I will describe a new semi-random model for graph partitioning problems and present a constant factor approximation algorithm for semi-random instances of Balanced Cut.  I will also mention our results for semi-random instances of other combinatorial optimization problems.

 

Joint work with Konstantin Makarychev (Microsoft Research) and Aravindan Vijayaraghavan (Princeton and CMU)

 

*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*

 

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20121016/7ebeb6e9/attachment.htm