| 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 Upson 215 from 10:10 to 11:25AM.
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.
| Aug 23 | No class. |
|---|---|
| Aug 28 | Course overview. Maximum flow problem; minimum s-t cuts, residual graphs. |
| Aug 30 | Maximum flow: optimality conditions. Applications of maximum flow: carpool fairness. |
| Sept 4 | Applications of maximum flow: baseball elimination. Efficient max flow algorithms: Most improving paths. |
| Sept 6 | Efficient max flow algorithms: Capacity scaling, push/relabel. |
| Sept 11 | Efficient max flow algorithms: Push/relabel. Highest label push/relabel. |
| Sept 13 | Tricks for push/relabel. Finding a min s-cut via push/relabel: the Hao-Orlin algorithm. |
| Sept 18 | Global minimum cuts: MA orderings. |
| Sept 20 | Global minimum cuts: random contraction algorithm. |
| Sept 25 | More maximum flow algorithms: blocking flows, Dinitz's algorithm, unit capacity graphs. |
| Sept 27 | More maximum flow algorithms: the Goldberg-Rao algorithm. |
| Oct 2 | Minimum-cost circulations: Definitions, optimality conditions. |
| Oct 4 | Minimum-cost circulations: Minimum-mean cycle canceling. |
| Oct 9 | Fall break: No class. |
| Oct 12 | Minimum-cost circulations: Strongly polynomial analysis of minimum-mean cycle canceling. |
| Oct 16 | Minimum-cost circulations: Wallacher's algorithm. |
| Oct 18 | Minimum-cost circulations: Cost scaling. |
| Oct 23 | No class. |
| Oct 25 | Minimum-cost circulations: Capacity scaling. |
| Oct 30 | Applications of minimum-cost circulations: Max flow over time. |
| Nov 1 | Minimum-cost circulations: Network simplex. Generalized flow: Definitions. |
| Nov 6 | Generalized flow: Optimality conditions. |
| Nov 8 | Generalized flow: A Wallacher-style GAP-canceling algorithm. |
| Nov 13 | Multicommodity flow: Intro, the Garg-Könemann algorithm. |
| Nov 15 | Multicommodity flow: the Awerbuch-Leighton algorithm. |
| Nov 20 | Network coding. |
| Nov 22 | No class: Thanksgiving break. |