Aaron Sidford - Recent Advances on the Maximum Flow Problem

From Katie Gentilello October 9th, 2021

21 plays 0 comments

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.

Tags: arc colloquiumalgorithms and randomness centergeorgia techrecorded by gtlibraryfall 2021

name: Aaron Sidford
Date: October 4th, 2021
Appears In: Open Scholarship

Comments
Related Media

Loading…

Aaron Sidford - Recent Advances on the Maximum Flow Problem

Related Media