Calendar

SES # TOPICS KEY DATES
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