Instructor: | David P. Williamson |
---|---|
Office: | Rhodes 236 |
Office hours: | Tuesdays 11-12, Thursdays |
Office phone: | 255-4883 |
Email: | davidpwilliamson AT cornell.edu |
The course meets Mondays and Wednesdays in Olin 255 from 1:25PM to 2:40PM.
This course will introduce students to the basic problems in network flow theory, and polynomial-time algorithms for solving them. The focus will be on the analysis of these polynomial-time algorithms, and some common themes in approaching network flow problems; that being said, flow problems are amenable to a surprising variety of approaches, and we will look at several of them. The bulk of the course will cover finding maximum flows, minimum global cuts, minimum-cost circulations, maximum generalized flows, maximum multicommodity flows, and flows over time. As time permits, we will also cover more advanced topics, including applications of flows to problems in computer science and coding theory, submodular function minimization, parametric maximum flow, and uses of randomization in flow algorithms.
Sept 2 | Course overview. Maximum flow problem; minimum s-t cuts, residual graphs, optimality conditions. (W 2.1) (Video) |
---|---|
Sept 7 | Maximum flow: Integrality. Types of polynomial time. Applications of maximum flow: maximum densest subgraph. (W 2.1, 2.4) (Video) |
Sept 9 | Efficient max flow algorithms: Most improving paths, capacity scaling. (W 2.5, 2.6) (Video) |
Sept 14 | Efficient max flow algorithms: Push-relabel. (W 2.8) (Video) |
Sept 16 | Efficient max flow algorithms: Push-relabel. Highest label push-relabel. Some heuristics. (W 2.8) (Video) |
Sept 21 | Global minimum cut problem. The Hao-Orlin algorithm. (W 3.1) (Video) (Missing proofs: Video, Notes) |
Sept 23 | Global minimum cuts: MA orderings. (W 3.2) (Video) |
Sept 28 | Global minimum cuts: random contraction algorithm, recursive random contraction. (W 3.3; Karger, W 2021) (Video) |
Sept 30 | Gomory-Hu trees. (W 3.4) (Video) |
Oct 5 | More maximum flow algorithms: blocking flows, Dinitz's algorithm, unit capacity graphs. (W 4.1, 4.2) (Video) |
Oct 7 | More maximum flow algorithms: the Goldberg-Rao algorithm. (W 4.3) (Video) (Missing proof: Video, Notes) |
Oct 12 | Minimum-cost circulations: Definitions, optimality conditions. (W 5.1) (Video) |
Oct 14 | No class: Fall break. |
Oct 19 | Minimum-cost circulations: Cycle canceling algorithms. Minimum-mean cycle canceling. (W 5.1, 5.3) (Video) |
Oct 21 | Minimum-cost circulations: Strongly polynomial analysis of minimum-mean cycle canceling. (W 5.3) (Video) (Missing proof: Video, Notes) |
Oct 26 | Minimum-cost circulations: Wallacher's algorithm. (W 5.2) (Video) |
Oct 28 | Minimum-cost circulations: Successive approximation. (W 5.5) (Video) |
Nov 2 | Minimum-cost circulations: Successive approximation. (W 5.5) (Video) |
Nov 4 | Minimum-cost circulations: Network simplex. Flows over time. (W 5.6, 5.7) (Video) |
Nov 9 | Application of minimum-cost circulations: Flows over time. (W 5.7) (Video) |
Nov 11 | Generalized flow: Optimality conditions. (W 6.1) (Video) (Missing proof: Video, Notes) |
Nov 16 | No class: Semi-finals period. |
Nov 18 | No class: Semi-finals period. |
Nov 23 | No class: Semi-finals period. |
Nov 25 | No class: Thanksgiving break. |
Nov 30 | Generalized flow: A Wallacher-style GAP-canceling algorithm. (W 6.2) (Video) |
Dec 2 | Generalized flow: A Wallacher-style GAP-canceling algorithm. (W 6.2) (Video) |
Dec 7 | Multicommodity flows. The Multiplicative Weight Update algorithm (W 7.1, 7.3) (Video) |
Dec 9 | Multicommodity flows: the Garg-Könemann algorithm (W 7.4) (Video) |
Dec 14 | Multicommodity flows: the Awerbuch-Leighton algorithm (W 7.5) (Video) |
Dec 16 | Open questions (W 9) |