Sept 1 |
Introduction to approximation algorithms. Introduction to the techniques: set cover. LP rounding, dual rounding. (Chap 1 of WS) |
Sept 3 |
Introduction to the techniques: set cover: Primal-dual, greedy. Greedy and local search algorithms: Maximizing bank float (Chap 1, 2 of WS) |
Sept 8 |
Greedy and local search algorithms: Maximizing submodular functions. Minimum maximum-degree spanning trees. (Chap 2 of WS) |
Sept 10 |
Greedy and local search algorithms: Minimum maximum-degree spanning trees. Rounding data and dynamic programming: knapsack (Chap 2, 3 of WS) |
Sept 15 |
Rounding data and dynamic programming: knapsack, bin packing. (Chap 3 of WS) |
Sept 17 |
Deterministic rounding of linear programs: bin packing. (Chap 4 of WS) |
Sept 22 |
Randomized rounding of linear programs: the maximum satisfiability problem. (Chap 5 of WS) |
Sept 24 |
Randomized rounding of linear programs: the maximum satisfiability problem. Randomized rounding of semidefinite programs: the maximum cut problem (Chaps 5, 6 of WS) |
Sept 29 |
Randomized rounding of semidefinite programs: the maximum cut problem. Quadratic programs. (Chap 6 of WS) |
Oct 1 |
Deterministic and randomized rounding of linear programs: the uncapacitated facility location problem (Chaps 4,5 of WS) |
Oct 6 |
The primal-dual method: Generalized Steiner tree. (Chap 7 of WS) |
Oct 8 |
The primal-dual method: the uncapacitated facility location problem. (Chap 7 of WS) |
Oct 15 |
Cuts and metrics: the multiway cut problem. (Chap 8 of WS) |
Oct 20 |
Cuts and metrics: the multicut problem. (Chap 8 of WS) |
Oct 22 |
Cuts and metrics: probabilistic embedding of metrics into tree metrics. (Chap 8 of WS) |
Oct 27 |
Further deterministic rounding: bounded-degree spanning trees. (Chap 11 of WS) |
Oct 29 |
Further deterministic rounding: bounded-degree spanning trees. (Chap 11 of WS) |
Nov 3 |
Further greedy and local search: uncapacitated facility location. (Chap 9 of WS) |
Nov 5 |
Further greedy and local search: the k-median problem. (Chap 9 of WS) |
Nov 10 |
Further rounding of semidefinite programs: Coloring 3-colorable graphs. (Chaps 6, 13 of WS) |
Nov 12 |
Further rounding of semidefinite programs: Coloring 3-colorable graphs. Unique games. (Chap 13 of WS) |
Nov 17 |
Further rounding of semidefinite programs: Unique games. (Chap 13 of WS) |
Nov 19 |
Further deterministic rounding: Survivable network design. (Chap 11 of WS) |
Nov 24 |
Further cuts and metrics: Oblivious routing. (Chap 15 of WS) |
Dec 1 |
Further cuts and metrics: the minimum bisection problem. (Chap 15 of WS) |
Dec 3 |
Course conclusion and open problems. |