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 ~~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.

Lecture Notes on Network Flow (Spring 2004)

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. |