The area of approximation algorithms is aimed at giving provable guarantees on the performance of heuristics for hard problems. The course will present general techniques (such as convex programming-based approaches, randomness and metric methods) that underly these algorithms.
Grading will be based on
There is no required book for the course, and papers/surveys will be provided on the course page, or handed out in class. The book Approximation Algorithms by V.V.Vazirani serves as an accessible introduction to the field.
Last updated: 03/15/2005