Lectures

The preliminary draft of Vazirani's book is available
here

1. August 26, 2008 Introduction, Vertex cover, maximal matching

2. August 28, 2008 Complexity classification, NP-hard problems, Local Ratio technique

3. Sept. 2, 2008 Local Ratio technique and Set Cover

4. Sept. 4, 2008 Set Cover and Minimum Steiner Tree

5. Sept. 9, 2008 Minimum Steiner Tree and Traveling Salesman

6. Sept. 11, 2008 Traveling Salesman (cont.)

7. Sept. 16, 2008 Multiway cut and k-cut

8. Sept. 18, 2008 k-cut (cont.) and k-center

9. Sept. 23, 2008 k-center (cont.)

Sept. 23, 2008 (notes format)

10.-11. Sept. 25, and 30 2008 Knapsack, bin packing

12-13. Oct. 2 and 7 2008 Restricted Shortest path Reference D. Lorenz and D. Raz A Simple Efficient Approximation Scheme for the Restricted Shortest Path Problem

14-18. Oct. 9, 21, 23, and 28. Linear programming, rounding techniques, and primal-dual schema

19. Nov. 4. Steiner Forest

20. Nov. 4. Network reliability