Research Institute for Discrete Mathematics

Module "Advanced Topics in Discrete Mathematics (V5C1)"

Lecture Course

New Network Flow Algorithms

Summer term 2020

Network flows is a classical topic in combinatorial optimization, studied since the 1950s. Still, new and better algorithms are being developed, even for the classical maximum flow problem. We will also discuss some extensions, such as multiflows, generalized flows, and electrical flows. For example, we will discuss Orlin's O(mn)-time max-flow algorithm in detail, as well as the recent strongly polynomial generalized flow maximization algorithm by Olver and Végh and the electrical flow approach by Christiano et al.

This course will be taught in English via Zoom. There will be no formal exercises. An introduction to the subject can be found, for example, in Chapter 8 of our combinatorial optimization book or in the classical Ahuja-Magnanti-Orlin book. Everyone who has read and understood this chapter should be able to follow the course, although it will be taught at an advanced level.

Further reading material:

Class Hours: Thursdays 10:15-11:45 and Fridays 12:15-13:45
Venue: online, on Zoom; see meeting number and password on eCampus
Exams: Oral exams on July 23 via Zoom, and on September 29.

Professor J. Vygen