Aaron Sidford - Recent Advances on the Maximum Flow Problem

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