Chennai Mathematical Institute

Seminars




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.





Google
Search WWW Search cmi.ac.in