ORIE 633: Network Flows

Fall 2007

Instructor Information

Instructor: David P. Williamson
Office: Rhodes 236
Office hours: M 1:30-2:30, W 11-12, and by appointment
Office phone: 255-4883
Email: My three initials AT cs.cornell.edu


The course meets Tuesdays and Thursdays in Olin 216 Upson 109 from 11:40 to 12:55.

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 economics, game theory, and coding theory, submodular function minimization, and uses of randomization in flow algorithms.


Handout 1: Course Information
Lecture Notes on Network Flow (Spring 2004)

Scribing materials

LaTeX macros for scribing
ZIP file with sample scribe notes


Aug 23 Course overview. Maximum flow problem; minimum s-t cuts, residual graphs, flow optimality conditions.
Aug 28 Applications of maximum flow: baseball elimination, carpool fairness.
Aug 30 Efficient max flow algorithms. Maximum capacity paths, capacity scaling.
Sept 4 Efficient max flow algorithms: push/relabel.
Sept 18 Review of push/relabel. FIFO push/relabel. Global min-cuts via min s-cuts.
Sept 20 Min s-cuts via push/relabel: the Hao-Orlin algorithm.
Sept 25 Global cuts in undirected graphs: MA orderings. Random contraction.
Sept 27 Global cuts in undirected graphs: Recursive random contraction. Efficient max flow algorithms: blocking flow.
Oct 2 Efficient max flow algorithms: blocking flow. Dinic's algorithm. Unit capacity graphs. The Goldberg-Rao algorithm.
Oct 4 Efficient max flow algorithms: The Goldberg-Rao algorithm.
Oct 11 Minimum-cost flows and circulations: their equivalence. Optimality conditions. Klein's algorithm.
Oct 16 Efficient min-cost circulation algorithms: the Goldberg-Tarjan min mean-cost cycle cancelling algorithm.
Oct 18 Efficient min-cost circulation algorithms: a strongly polynomial-time analysis of the min mean-cost cycle cancelling algorithm.
Oct 23 Efficient min-cost circulation algorithms: Cost scaling.
Oct 25 Efficient min-cost circulation algorithms: Cost scaling. Capacity scaling.
Oct 30 Efficient min-cost circulation algorithms: Capacity scaling. Generalized flow: definitions.
Nov 1 Generalized flow: Optimality conditions. Truemper's algorithm.
Nov 6 Generalized flow: Truemper's algorithm. Gain scaling. Error scaling.
Nov 8 Flows over time: maximum s-t flow over time.
Nov 13 Multicommodity flow: Definitions. The cut condition and its insufficiency in general. Two commodity flows.
Nov 15 Multicommodity flow: the Garg-Könemann algorithm.
Nov 20 Multicommodity flow: the Awerbuch-Leighton algorithm.
Nov 27 The edge-disjoint path problem: Kleinberg's approximation algorithm. Hardness of approximation.
Nov 29 Single-source unsplittable flow: An approximation algorithm.
Dec 4 More efficient min-cost circulation algorithms: Wallacher's algorithm(s).
Dec 6 Generalized min-cost circulations: Wayne's algorithm. Some open questions in network flow.

Problem Sets