Time: Tuesdays, 14:00-17:00

Place: Schrieber 7

The course will cover approximation algorithms for NP-hard optimization problems. Among the problems considered: metric TSP, set cover, vertex cover, bin packing, routing problems, constraint satisfaction problems such as MAX CUT and MAX SAT, coloring 3-colorable graphs, multi-cuts and multiway cuts and network design problems.

Some Scribe notes

Lecture notes on Approximation Algorithms

- Approximation Algorithms, Cornell, Fall 98 (Lecturer: David Williamson)
- Approximation Algorithms for Network Problems, Sep. 98 (Lecturers: J. Cheriyan and R. Ravi)
- Approximation Algorithms, MIT, Fall 94 (Lecturer: Michel Goemans)

- Approximation Algorithms, Fields Institute, Fall 99 (Lecturer: Joseph Cheriyan)
- Approximability of Optimization Problems, MIT, Fall 99 (Lecturer: Madhu Sudan)
- Topics in Mathematical Programming: Approximation Algorithms, Cornell, Spring 99 (Lecturer: David Shmoys)
- Approximation Algorithms, Johns Hopkins, Fall 98 (Lecturer: Lenore Cowen)
- Approximation Algorithms, Technion, Fall 95 (Lecturer: Yuval Rabani)

- Approximation Algorithms for Bin Packing: A Survey (E.G. Coffman, M.R. Garey, D.S. Johnson)
- The Primal-Dual method (Michel Goemans and David Williamson)

Dorit S. Hochbaum (Editor)

Approximation Algorithms for NP-hard
problems

PWS Publishing Company, 1997

Relevant Home Pages