New Network Flow Algorithms

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.

• D. Williamson: Network Flow Algorithms. Cambridge University Press 2019 (available online here)
• R. Ahuja, T. Magnanti, J. Orlin: Network Flows. Prentice-Hall 1993
• R. Tarjan: Data Structures and Network Algorithms. SIAM 1983
• D. Sleator, R. Tarjan: A data structure for dynamic trees. Journal of Computer and System Sciences 26 (1983), 362-391
• D. Sleator, R. Tarjan: Self-adjusting binary trees. Journal of the ACM 32 (1985), 652-686
• A. Goldberg, S. Rao: Beyond the flow decomposition barrier. Journal of the ACM 45 (1998), 783-797
• G. Italiano: Amortized efficiency of a path retrieval data structure. Theoretical Computer Science 48 (1986), 273-281
• J. Orlin: Max flow in O(mn) time, or better. Proceedings of STOC 2013, 765-774
• A. Goldberg, R. Tarjan: A new approach to the maximum flow problem. Journal of the ACM 35 (1988), 921-940
• J. Cheriyan, T. Hagerup, K. Mehlhorn: An $o(n^3)$-time maximum-flow algorithm. SIAM Journal on Computing 25 (1996), 1144-1170
• V. King, S. Rao, R. Tarjan: A faster deterministic maximum flow algorithm. Journal of Algorithms 17 (1994), 447-474
• L. Végh: A strongly polynomial algorithm for generalized flow maximization. Mathematics of Operations Research 42 (2017), 179-211
• N. Olver, L. Végh: A simpler and faster strongly polynomial algorithm for generalized flow maximization. Journal of the ACM 67 (2020), Article 2
• J. Kelner, L. Orecchia, A. Sidford, Z. Zhu: A simple, combinatorial algorithm for solving SSD systems in near-linear time. arXiv:1301.6628; extended abstract in the Proceedings of STOC 2013, 911-920
• P. Christiano, J. Kelner, A. Mądry, D. Spielman, S.-H. Teng: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. arXiv 1010.2921v2; extended abstract in the Proceedings of STOC 2011, 273-281
• A. Mądry: From graphs to matrices, and back: new techniques for graph algorithms. PhD thesis, MIT, 2011
• A. Mądry: Computing maximum flow with augmenting electrical flows. arXiv:1608.06016; extended abstract in the Proceedings of FOCS 2016, 593-602

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.