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) LP-Rounding: Minimizing Congestion and Chernoff Bounds (Sec 5.10-5.11)

8. (9/26) LP-Duality and Primal-Dual Algorithms (Appendix A, Sec 7.1)

9. (9/30) Primal-Dual: Shortest Path (Sec 7.3)

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

11. (10/7)  Cuts and Metrics: Introduction

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

13. (10/14) Cuts and Metrics: Multiway Cut (Sec 8.1-8.2)

14. (10/14) Cuts and Metrics: Sparsest Cut (Sec 15.1)

15. (10/21)  Intro to Semidefinite Programming (SDP), Max-Cut (Sec 6.1-6.2)

16. (10/24)  SDP Rounding: Max 2SAT

17. (10/28)   SDP Rounding: Correlation Clustering (Sec 6.4)

18. (10/31)   SDP Rounding: Coloring 3-colorable graphs (Sec 6.5)

19. (11/4)   Greedy Algorithms: TSP, Set Cover (Sec 1.6)

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

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

22. (11/14)   Local Search: Max-Cut

23. (11/18)   Local Search: k-Median (Sec 9.2) 

24. (11/21) Polynomial-Time Approximation Schemes (PTAS) (Sec 3.1)

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) Hardness of Approximation: PCP Theorems cont'd

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