15-854 Approximation Algorithms, Fall 2005

15-854: Approximation Algorithms

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

homework assignments (at least 4),

a take-home final, and

class participation (which includes scribe notes for lectures).

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