Class Schedule
(subject to change at any time)
(8/29) Introduction: Vertex Cover, TSP (Sec 2.4)
(9/2) Metric TSP, Christofides algorithm (Sec 2.4)
(9/9) Introduction to Linear Programming (Appendix A, Sec 4.3)
(9/12) LP-Rounding: Set Cover (Sec 1.2-1.3, 1.7)
(9/16) LP-Rounding: MAX-SAT (Sec 5.1, 5.4-5.6)
(9/19) LP-Rounding: MAX-SAT continued, Minimizing Congestion (Sec 5.10-5.11)
(9/23) No class today
(9/26) LP-Rounding: Minimizing Congestion and Chernoff Bounds (Sec 5.10-5.11)
(9/30) LP-Duality and Primal-Dual Algorithms (Appendix A)
(10/3) Primal-Dual: Set Cover and Vertex Cover, Shortest Path (Sec 7.1, 7.3)
(10/7) Primal-Dual: Shortest Path, Steiner Forest (Sec 7.3, 7.4)
(10/10) Midterm Exam (in class)
(10/14) Cuts and Metrics: Introduction
(10/17) Cuts and Metrics: Multicut (Sec 8.3)
(10/21) Cuts and Metrics: Multiway Cut (Sec 8.1-8.2)
(10/24) Intro to Semidefinite Programming (SDP), Max-Cut (Sec 6.1-6.2)
(10/28) SDP Rounding: Max 2SAT
(10/31) SDP Rounding: Correlation Clustering (Sec 6.4)
(11/4) Greedy Algorithms: TSP, Set Cover (Sec 1.6)
(11/7) Greedy Algorithms: Submodular functions/Max Coverage (Sec 2.5)
(11/11) Greedy Algorithms: k-Center (Sec 2.2)
(11/14) Local Search: Max-Cut
(11/18) Local Search: k-Median (Sec 9.2)
(11/21) Polynomial-Time Approximation Schemes (PTAS) (Sec 3.1)
(12/2) Hardness of Approximation: Gap-Preserving Reductions (Sec 16.1-16.2)
(12/5) Hardness of Approximation: PCP Theorems (Sec 16.3)
(12/9) No class today
(12/12) Unique Games Conjecture, Self-Reducibility