Network Flows (MA5518)
lecture

Network flows are a central concept in combinatorial optimization, with many important applications in areas such as transportation, communication, or production. This course covers advanced network flow topics that extend upon the basic max flow and min cost flow problems:
  • 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

Literature