• multicommodity flows
• flows over time
• robust flows
• generalized flows
• flow computation in planar graphs

News

• The course is over, thank you for participating!

Schedule

Lectures

Tutorial Classes

Lecture notes/slides

• Lecture 1 (April 19, 2016): maximum flow problem, max flow/min cut, augmenting path algorithm, flow decomposition, capacity scaling. Suggested reading: Sec. 8.1 of Korte-Vygen; Lecture 5 of David Williamson's course
• Lecture 2 (April 26, 2016): push/relabel algorithm. Suggested reading: Sec. 8.5 of Korte-Vygen
• Lecture 3 (May 3, 2016): minimum cost flow problem, minimum mean cycle canceling algorithm. Suggested reading: Sec 9.1-9.3 of Korte-Vygen
• Lecture 4 (May 10, 2016): running time of minimum mean cycle canceling algorithm. Suggested reading: Sec 9.3 of Korte-Vygen
• Lecture 5 (May 24, 2016): successive shortest path algorithm, multicommodity flows. Suggested reading: Sec 9.4 and 19.1 of Korte-Vygen
• Lecture 6 (May 31, 2016): FPTAS for maximum multicommodity flow. Suggested reading: Sec 19.2 of Korte-Vygen
• Lecture 7 (June 2, 2016): cut and distance criterion for multicommodity flows, arc-disjoint paths problem, flows over time. Suggested reading: Sec 19.1 of Korte-Vygen, Sec 1-2 of Skutella's Introduction to Network Flows Over Time.
• Lecture 8 (June 14, 2016): algorithm for the maximum flow over time problem, max flow/min cut over time, earliest arrival flows. Sec 1-3 of Skutella's Introduction to Network Flows Over Time.
• Lecture 9 (June 16, 2016): earliest arrival flow algorithm, minimum cost flows over time. Sec 3-4 of Skutella's Introduction to Network Flows Over Time; if you want to see earliest arrival flows in action, try out the ZET Evacuation Tool .
• Lecture 10 (June 21, 2016): time-expanded networks, multicommodity flows over time. Suggested reading: Sec 4-5 of Skutella's Introduction to Network Flows Over Time and the article  by Groß and Skutella on speed-up through storage for multi-commodity flows.
• Lecture 11 (June 28, 2016): robust flows. Suggested reading: Lecture notes on robust flows.
• Lecture 12 (July 12, 2016): maximum flows in planar graphs. Suggested reading: Borradaile & Klein's article , Sections 2.3 & 4 of Lattices and maximum flows in planar graphs .

Problem sets

• Problem set 1 (Discussion: April 28, 2016; solutions)
• Problem set 2 (Discussion: May 12, 2016; solutions)
• Problem set 3 (Discussion: June 9, 2016; solutions)
• Problem set 4 (Discussion: June 23, 2016; solutions)

Literature

• B. Korte, J. Vygen. "Combinatorial Optimization: Theory and Algorithms". Springer, 2012.
• R. Ahuja, T. Magnanti, J. Orlin. "Network flows, Theory, Algorithms, and Applications". Prentice Hall, 1993.
• D. Williamson. "Lecture Notes on Network Flow Algorithms ". Cornell University, 2014.
• M. Skutella. "An Introduction to Network Flows Over Time" , in W. Cook, L. Lovász and J. Vygen (eds.): Research Trends in Combinatorial Optimization, pp. 451-482, Springer, 2009.
• The website of the ZET Evacuation Tool  contains software for computing and visualising earliest arrival flows and useful examples.
• M. Groß, M. Skutella. "A tight bound on the speed-up through storage for quickest multi-commodity flows" . Operations Research Letters 43.1:93-95, 2015.
• Lecture notes on robust flows (Lecture 11)
• G. Borradaile, P. Klein. An O(n log n)-algorithm for maximum s-t-flow in a directed planar graph . Journal of the ACM 56(2), 2009.