CSE 522, Autumn 2009: Approximation Algorithms

This quarter we will study the design and analysis of approximation algorithms for NP-hard problems, specifically approximation algorithms based on linear and semidefinite programming. For at least half the course we will be using a new, unpublished book by David Williamson and David Shmoys that I will be handing out in class.

I am definitely planning on covering most of chapter 1, Sections 6.1, 6.2, 7.1-7.4, 8.3-8.6, 11.2, and chapter 15. If time permits, I will cover other portions of Chapter 6, 8, 13 and 15.

I am working on a list of open problems. It is very much under construction.


Lecture topics with readings, references and, occasionally, lecture notes: