12.00 hrs. Hardness of approximation and Unique games conjecture Preyas Popat New York University, U.S.A. 11-01-12 Abstract This talk will be a survey of certain approximation algorithms and hardness results in the last two decades, beginning with the Goemans-Williamson algorithm for Max Cut and moving on to hardness results based on the Unique games conjecture. Most of the talk should be accessible to an undergraduate audience.
|