ORIE 6330: Network Flows

Fall 2015

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 Phillips 213 Hollister 306 from 11:40AM to 12:55PM.

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
Lecture Notes on Network Flow (Spring 2004)

Lectures

Aug 25 Course overview. Maximum flow problem; minimum s-t cuts, residual graphs, optimality conditions.
Aug 27 Maximum flow: Integrality. Types of polynomial time. Applications of maximum flow: maximum densest subgraph.
Sept 1 Applications of maximum flow: baseball elimination. Efficient max flow algorithms: Most improving paths.
Sept 3 Efficient max flow algorithms: Most improving paths, capacity scaling.
Sept 8 Efficient max flow algorithms: Push-relabel.
Sept 10 Efficient max flow algorithms: Push-relabel. Highest label push-relabel.
Sept 15 Global minimum cuts: MA orderings.
Sept 17 Global minimum cuts: random contraction algorithm.
Sept 22 More maximum flow algorithms: blocking flows, Dinitz's algorithm, unit capacity graphs.
Sept 24 More maximum flow algorithms: the Goldberg-Rao algorithm.
Sept 29 Minimum-cost circulations: Definitions, optimality conditions.
Oct 1 Minimum-cost circulations: Minimum-mean cycle canceling.
Oct 6 Minimum-cost circulations: Strongly polynomial analysis of minimum-mean cycle canceling.
Oct 8 Minimum-cost circulations: Wallacher's algorithm.
Oct 13 Fall break: No class.
Oct 15 Minimum-cost circulations: Cost scaling.
Oct 20 Applications of minimum-cost circulations: Max flow over time.
Oct 22 Minimum-cost circulations: Network simplex. Generalized flow: Definitions.
Oct 27 Generalized flow: Optimality conditions.
Oct 29 Generalized flow: A Wallacher-style GAP-canceling algorithm.
Nov 3 Multicommodity flow: Intro, Multiplicative Weights, and the Garg-Könemann algorithm.
Nov 5 Multicommodity flow: the Awerbuch-Leighton algorithm.
Nov 10 Network coding.
Nov 12 Electrical flows and graph Laplacians. Cut sparsifiers.
Nov 17 No class.
Nov 19 No class.
Nov 24 Electrical flows and spectral sparsifiers.
Nov 26 Thanksgiving: No class.
Dec 1 Multiplicative Weights and packing problems. Maximum flow via electrical flows.
Dec 3 Open problems.

Problem Sets