- multicommodity flows
- flows over time
- robust flows
- generalized flows
- flow computation in planar graphs
Lecturer: | Jannik Matuschke |
---|---|
weekly hours: | 2+1 hours |
ECTS credits: | 5 |
News | Schedule | Lecture notes | Problem sets | Literature |
News
- The course is over, thank you for participating!
Schedule
Lectures
Day | Time | Room | Lecturer |
---|---|---|---|
Tue | 16:00-17:30 | 00.07.014 | Jannik Matuschke |
Tutorial Classes
Day | Time | Room | Lecturer |
---|---|---|---|
Thu (biweekly) | 10:15-11:45 | 03.08.011 | Jannik Matuschke |
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.