Guy Kortsarz's Home Page

Slide notes on approximation algorithms:

Part I. Background

For a postscript file

Part II. Basic approximation algorithms

For a postscript file

Part III. Advanced algorithms: cut problems

For a postscript file

Planned: two more parts.

Part IV: Random methods. Randomized rounding,
the Bartal result, Group Steiner, semidefinite methods,
The GW max-cut algorithm, and the 3-coloring problem
Only the slides on the Bartal theorem are ready;

For a postscript file

Part V: Geometric algorithms, the PTAS for
geometric TSP. Lower bounds: clique, coloring lb via
zero knowledge, lower bound for set-cover via one round
two provers. Lower bound for set covers in k-uniform
hypergraphs: a k-1-epsilon lower bound