| 1 | Introduction | |
| 2 | LINEAR PROGRAMMING (LP): basic notions, simplex metho | |
| 3 | LP: Farkas Lemma, duality
| Problem set 1 due |
| 4 | LP: complexity issues, ellipsoid method | |
| 5 | LP: ellipsoid method | |
| 6 | LP: optimization vs. separation, interior-point algorithm | |
| 7 | LP: optimality conditions, interior-point algorithm (analysis) | |
| 8 | LP: interior-point algorithm wrap up
NETWORK FLOWS (NF) | Problem set 2 due |
| 9 | NF: Min-cost circulation problem (MCCP) | |
| 10 | NF: Cycle cancelling algs for MCCP | |
| 11 | NF: Goldberg-Tarjan alg for MCCP and analysis | Problem set 3 due |
| 12 | NF: Cancel-and-tighten DATA STRUCTURES (DS): Binary search trees | |
| 13 | DS: Splay trees, amortized analysis, dynamic trees | |
| 14 | DS: dynamic tree operations | |
| 15 | DS: analysis of dynamic trees NF: use of dynamic trees for cancel-and-tighten
| |
| 16 | APPROXIMATION ALGORITHMS (AA): hardness, inapproximability, analysis of approximation algorithms | Problem set 4 due |
| 17 | AA: Vertex cover (rounding, primal-dual), generalized Steiner tree | |
| 18 | AA: Primal-dual alg for generalized Steiner tree | |
| 19 | AA: Derandomization | |
| 20 | AA: MAXCUT, SDP-based 0.878-approximation algorithm | |
| 21 | AA: Polynomial approximation schemes, scheduling problem: P||Cmax | |
| 22 | AA: Approximation Scheme for Euclidean TSP | Problem set 5 due |
| 23 | AA: Multicommodity flows and cuts, embeddings of metrics | Problem set 6 due |