Approximability of Optimization Problems

A complexity-theoretic view of combinatorial optimization.

Prereq: 6.042, 6.045, 6.046.
Instructor: Madhu Sudan
Time: MW 2:30-4:00pm
Location: 24-307
3-0-9 H-Level Grad Credit
Course announcement


I'll be adding material here as we go along. For now here are some sources for approximation algorithms; and hardness of approximations.

Topics covered so far:

For future scribes, here is a sample file and the preamble.tex file that it uses.