ORIE 6330: Network Flows

Fall 2020

Instructor Information

Instructor: David P. Williamson
Office: Rhodes 236
Office hours: Tuesdays 11-12, Thursdays 3-4 2:30-3:30, and by appointment
Office phone: 255-4883
Email: davidpwilliamson AT cornell.edu

Overview

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.

Handouts

Handout 1: Course Information

Book

The text is Network Flow Algorithms, published by Cambridge University Press. A PDF of the book can be downloaded here.

Lectures

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)

Problem Sets