Recent Advances on the Maximum Flow Problem

Presented online via Bluejeans Meetings on October 4, 2021 at 11:00 a.m.Aaron Sidford is an assistant professor of Management Science and Engineering and, by courtesy, of Computer Science at Stanford University. His research interests lie broadly in optimization, the theory of computation, and the design and analysis of algorithms. He is particularly interested in work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures.Runtime: 66:49 minutesThe maximum flow problem is an incredibly well-studied problem in combinatorial optimization. The problem encompasses a range of cut, matching, and scheduling problems and is a key a proving ground for new techniques in continuous optimization and algorithmic graph theory. In this talk I will survey recent, provably faster algorithms for solving this problem. Further, I will highlight how recent advances in solving mixed l2-lp flows can be coupled with interior point methods to obtain improved running times for solving the problem on unit-capacity graphs. The maximum flow problem on unit capacity graphs encompasses fundamental combinatorial optimization problems including bipartite matching and computing disjoint paths and I will discuss how this line of work has led to state-of-the-art, almost m^(4/3) time algorithms for solving these problems on m-edge graphs. This talk focuses on joint work with Yang P. Liu and Tarun Kathuria