Date | Contents | References | Remarks | Scribe notes1 | Scribe | |
Lecture 1 | Mon Aug 28 | Introduction and administrivia Why Approximation Algorithms? Intractability, inefficiency, uncertainty Problems: Vertex cover Techniques: Local and global methods, Sampling and estimation, Linear programs Limits: integrality gaps, hardness of approximation |
Notes | Nat | ||
Lecture 2 | Wed Aug 30 | Local search/Greedy: Set cover, Submodular maximizaton, Precedence constraint scheduling, List scheduling | Notes | Nat | ||
Lecture 3 | Mon Sep 4 | Local search/Greedy: TSP, Clustering | Notes | Reza | ||
Lecture 4 | Wed Sep 6 | Dynamic programming/Data rounding: Knapsack, Bin packing | Notes | Harsh | ||
Mon Sep 11 | No class. Instructor travel. | |||||
Wed Sep 13 | No class. Instructor travel. | |||||
Lecture 5 | Mon Sep 18 | The primal-dual method: Vertex cover, Set cover, Feedback vertex set, Facility location | Notes | Xiang | ||
Lecture 6 | Wed Sep 20 | The primal-dual method: Facility location, k-median | Notes | Mark | ||
Lecture 7 | Mon Sep 25 | The primal dual method: k-median (cont.) Dual fitting: Vertex cover, Set cover |
Notes | Brandon | ||
Lecture 8 | Wed Sep 27 | Dual fitting: Facility location | Notes | Alex | ||
Lecture 9 | Wed Sep 27 | Randomized rounding: Set cover, Congestion minimization | Notes | Eli | ||
Lecture 10 | Mon Oct 2 | Randomized rounding: Congestion minimization (cont.), Max SAT | Notes | Aaron | ||
Lecture 11 | Wed Oct 4 | Randomized rounding: Max SAT (cont.) Deterministic rounding: Min cost matchings, Generalized assignment problem |
Notes | Kevin | ||
Mon Oct 9 | No class. Fall break. | |||||
Lecture 12 | Wed Oct 11 | Iterative rounding: Maximum weight matching, Minimum spanning tree | Notes | Hanrui | ||
Lecture 13 | Mon Oct 16 | Iterative rounding: Minimum spanning tree (cont.), Degree-bounded spanning tree | Notes | Shweta | ||
Lecture 14 | Wed Oct 18 | Iterative rounding: Degree-bounded spanning tree (cont.) Multiway cut |
Notes | Abe | ||
Lecture 15 | Mon Oct 23 | Multicuts, Multi-commodity flows Semi-definite programming: Maximum cut |
Notes | Erin | ||
Lecture 16 | Wed Oct 25 | Semi-definite programming: Maximum cut (cont.) Integrality gaps: Vertex cover, Set cover Dependent rounding: Group steiner tree |
Notes | Fred | ||
Lecture 17 | Mon Oct 30 | Dependent rounding: Group steiner tree (cont.) | Notes | Keerti | ||
Lecture 18 | Wed Nov 1 | Semi-definite programming: Graph coloring | Notes | Feng | ||
Lecture 19 | Mon Nov 6 | Metric embeddings | Notes | Xingyu | ||
Lecture 20 | Wed Nov 8 | Metric embeddings: Sparsest cut | Notes | Yuan | ||
Lecture 21 | Mon Nov 13 | Metric embeddings: Sparsest cut (cont.) | Notes | Kangning | ||
Lecture 22 | Wed Nov 15 | Semi-definite programming: Sparsest cut | ||||
Lecture 23 | Mon Nov 20 | Semi-definite programming: Sparsest cut (cont.) Online algorithms: Ski-rental, Set cover |
||||
Wed Nov 22 | No class. Thanksgiving recess. | |||||
Lecture 24 | Mon Nov 27 | Online algorithms: Set cover (cont.), Steiner tree | ||||
Lecture 25 | Wed Nov 29 | Hardness of approximation: PCP theorem and reductions |