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

Overview

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.

Handouts

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

Scribing materials

LaTeX macros for scribing
ZIP file with sample scribe notes

Lectures

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.