Class Schedule

(subject to change at any time)

1. (8/29) Introduction: Vertex Cover, TSP (Sec 2.4)

2. (9/2) Metric TSP, Christofides algorithm (Sec 2.4)

3. (9/9) Introduction to Linear Programming (Appendix A, Sec 4.3)

4. (9/12) LP-Rounding: Set Cover (Sec 1.2-1.3, 1.7)

5. (9/16) LP-Rounding: MAX-SAT (Sec 5.1, 5.4-5.6)

6. (9/19) LP-Rounding: MAX-SAT continued, Minimizing Congestion (Sec 5.10-5.11)

7. (9/23) No class today

8. (9/26) LP-Rounding: Minimizing Congestion and Chernoff Bounds (Sec 5.10-5.11)

9. (9/30) LP-Duality and Primal-Dual Algorithms (Appendix A)

10. (10/3) Primal-Dual: Vertex Cover and Set Cover (Sec 7.1)

11. (10/7) Primal-Dual: Shortest Path (Sec 7.3)

12. (10/10) Midterm Exam (in class)

13. (10/14) Primal-Dual: Steiner Forest (Sec 7.4)

14. (10/17) Cuts and Metrics: Introduction

15. (10/21) Cuts and Metrics: Multicut (Sec 8.3)

16. (10/24) Cuts and Metrics: Multiway Cut (Sec 8.1-8.2)

17. (10/28) Multiway Cut continued, Intro to Semidefinite Programming (SDP) (Sec 6.1)

18. (10/31) SDP Rounding: Max-Cut, Max 2SAT (Sec 6.2)

19. (11/4)   SDP Rounding: Correlation Clustering (Sec 6.4)

20. (11/7)   Greedy Algorithms: TSP, Set Cover (Sec 1.6)

21. (11/11)  Greedy Algorithms: Submodular functions/Max Coverage (Sec 2.5)

22. (11/14)  Greedy Algorithms: k-Center (Sec 2.2) 

23. (11/18)  Local Search: Max-Cut

24. (11/21)  Local Search: k-Median (Sec 9.2), PTAS? 

25. (12/2)  Hardness of Approximation: Gap-Preserving Reductions (Sec 16.1-16.2)

26. (12/5)  Hardness of Approximation: PCP Theorems (Sec 16.3)

27. (12/9)  No class today

28. (12/12) Unique Games Conjecture, Self-Reducibility