15-859(Q): Advanced Topics in Approximation Algorithms

Anupam Gupta and R. Ravi

Time: Friday 9:30A-12P, Wean 4615A

Course description:

This is a companion course to the Fall 2005 course on Approximation Algorithms. We will concentrate on advanced techniques in approximation algorithms, and hence will assume the previous course 15-854 as a pre-requisite.

The course will entail reading and presenting papers from recent conferences, and is aimed at understanding recent research in the field, with an eye towards obtaining improved results. Students will be evaluated based on presentations, and also based on their participation in class.

Announcements:

1. (2/1) See the course wiki for more details on the various lectures.

Papers/Topics Discussed

1. (Jan 20) Introduction, Approximations for Dense Instances. (Anupam)
2. (Jan 27) No class. (Sanjeev Arora speaking at Pitt.)
3. (Feb 3) Bicriteria Network Design. (Ravi)
4. (Feb 10) Online Algorithms. (Anupam)

Last updated: 1/19/2006