APPROXIMATION ALGORITHMS (0368.4042.01)

Fall 2001, Tel Aviv University

Mailing list: cs0368-4042-01@post.tau.ac.il

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 (Old) Scribe notes

Lectue 1
Lectue 2
Lectue 3

Coloring 3-colorable graphs

Some exercises

Hebrew exercises (Word 2000)
Same Hebrew exercises (RTF)

Take home exams

Exam (2000)

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 (by Vijay Vazirani)
• Approximation Algorithms (by Rajeev Motwani)

• 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

• Sanjeev Arora
• Joseph Cheriyan
• Michel Goemans
• Johan Hastad
• David Johnson
• David Karger
• Yuval Rabani
• R. Ravi
• David Shmoys
• Madhu Sudan
• Vijay Vazirani
• David Williamson