| Lect | Date | Topic | Reference |
| | Linear Programming | |
| 1 |
08/26 |
Theory of LP |
[MG4, Go9] |
| 2 |
08/28 |
Simplex and Other Algorithms |
[MG5, Go10] |
| 3 |
09/04 |
Duality |
[MG6] |
| | Network Optimization | |
| 4 |
09/09 |
Min-Cut Max-Flow |
[KT7, Eri10] |
| 5 |
09/11 |
Max-Flow Algorithms |
[KT7, Eri10] |
| 6 |
09/16 |
Min-Cost Max Flow |
[ErG, GT] |
| 7 |
09/18 |
Optimal Transport |
[Rg, CP] |
| | Approximation Algorithms | |
| 8 |
09/23 |
Vertex Cover, Set Cover |
[KT11, WS02,07] |
| 9 |
09/25 |
Clustering |
[WS02] |
| 10 |
09/30 |
Scheduling & Related Problems |
[WS03,04] |
| 11 |
10/02 |
Multiplicative Weight Method |
[AHK] |
| 12 |
10/07 |
Primal-Dual Method |
[WS07] |
| | Randomized Algorithms | |
| 13 |
10/09 |
Global Min-Cut |
[KT13] |
| Exam |
10/16 |
Midterm 1 (Lectures 1-12) |
|
| 14 |
10/21 |
LP Rounding |
[KT13, WS05] |
| 15 |
10/23 |
SDP Rounding |
[WS06]
|
| 16 |
10/28 |
Chernoff Bound, Discrepancy |
[MR04] |
| 17 |
10/30 |
Probabilistic Tree Embedding |
[WS10]
|
| | Similarity Search | |
| 18 |
11/04 |
Nearest-Neighbor Searching |
[HP11] |
| 19 |
11/06 |
Dimension Reduction |
[Mat15] |
| 20 |
11/11 |
Locality Sensitive Hashing |
[HP20] |
| | Algebraic/Numerical Algorithms | |
| 21 |
11/13 |
Polynomial Identity Testing |
[MR7] |
| 22 |
11/18 |
Gradient Descent Methods |
[BV9] |
| 23 |
11/20 |
Random Walk on Graphs |
[MR] |
| 24 |
11/25 |
Cheeger Inequality & Sparsest Cut |
[TBD] |
| Exam |
12/02 |
Midterm 2 (Lectures 13-24)
|
|