Course description:
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.
Admin:
Grading will be based on
Homeworks should be done without collaboration, except on questions that
are specifically marked "Collaboration allowed". Because this course has
no TA, students will also be asked to help with the grading of assignments
from time to time.
Readings:
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