|
|
 |
|
| 1 |
Course Introduction
Matching Theory |
|
| 2 |
The Hungarian Algorithm |
|
| 3 |
Edmonds' Algorithm |
|
| 4 |
Polyhedral Combinatorics |
|
| 5 |
The Matching Polytope I |
|
| 6 |
The Matching Polytope II |
|
| 7 |
Flow Theory and Duality |
|
| 8 |
Max-flow Algorithms |
Assignment 1 due |
| 9 |
Min-cut Algorithms |
|
| 10 |
Min-cost Flow |
|
| 11 |
Strongly Polynomial Algorithms |
|
| 12 |
Linear Programming Duality |
|
| 13 |
The Simplex Algorithm |
Assignment 2 due |
| 14 |
Exam I |
|
| 15 |
The Simplex Algorithm (contd.) |
|
| 16 |
Complementary Slackness
Primal-dual Algorithm |
|
| 17 |
The Ellipsoid Algorithm I: Ideas |
|
| 18 |
The Ellipsoid Algorithm II: Details |
|
| 19 |
Separation Oracles I: Convex Problems |
|
| 20 |
Oracles II: Combinatorial Problems |
|
| 21 |
NP-completeness |
Assignment 3 due |
| 22, 23 |
Approximation Algorithms |
|
| 24 |
The Relax-and-round Paradigm |
|
| 25 |
Exam II |
Assignment 4 due |
| 26, 27 |
Projects Reviews |
|
|
|
|
|
|
 |
|
