Fall 1999, Tel Aviv University

Lecturer: Uri Zwick
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

Coloring 3-colorable graphs

Lecture notes on Approximation Algorithms

  • Home Pages of Similar Courses
  • Monographs Chapters in Books Books

    Dorit S. Hochbaum (Editor)
    Approximation Algorithms for NP-hard problems
    PWS Publishing Company, 1997

    Relevant Home Pages