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