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.