[Colloquium] [Staff] Theory Seminars at Computer Science
Donna Brooms
donna at cs.uchicago.edu
Mon Oct 15 05:54:08 CDT 2012
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/20121015/6326e6a0/attachment.htm
More information about the Colloquium
mailing list