# ORIE 633: Network Flows

## Fall 2007

### Instructor Information

Instructor: David P. Williamson Rhodes 236 M 1:30-2:30, W 11-12, and by appointment 255-4883 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. Applications of maximum flow: baseball elimination, carpool fairness. Efficient max flow algorithms. Maximum capacity paths, capacity scaling. Efficient max flow algorithms: push/relabel. Review of push/relabel. FIFO push/relabel. Global min-cuts via min s-cuts. Min s-cuts via push/relabel: the Hao-Orlin algorithm. Global cuts in undirected graphs: MA orderings. Random contraction. Global cuts in undirected graphs: Recursive random contraction. Efficient max flow algorithms: blocking flow. Efficient max flow algorithms: blocking flow. Dinic's algorithm. Unit capacity graphs. The Goldberg-Rao algorithm. Efficient max flow algorithms: The Goldberg-Rao algorithm. Minimum-cost flows and circulations: their equivalence. Optimality conditions. Klein's algorithm. Efficient min-cost circulation algorithms: the Goldberg-Tarjan min mean-cost cycle cancelling algorithm. Efficient min-cost circulation algorithms: a strongly polynomial-time analysis of the min mean-cost cycle cancelling algorithm. Efficient min-cost circulation algorithms: Cost scaling. Efficient min-cost circulation algorithms: Cost scaling. Capacity scaling. Efficient min-cost circulation algorithms: Capacity scaling. Generalized flow: definitions. Generalized flow: Optimality conditions. Truemper's algorithm. Generalized flow: Truemper's algorithm. Gain scaling. Error scaling. Flows over time: maximum s-t flow over time. Multicommodity flow: Definitions. The cut condition and its insufficiency in general. Two commodity flows. Multicommodity flow: the Garg-Könemann algorithm. Multicommodity flow: the Awerbuch-Leighton algorithm. The edge-disjoint path problem: Kleinberg's approximation algorithm. Hardness of approximation. Single-source unsplittable flow: An approximation algorithm. More efficient min-cost circulation algorithms: Wallacher's algorithm(s). Generalized min-cost circulations: Wayne's algorithm. Some open questions in network flow.