*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Aaron Sidford (Stanford)
Monday, October 4, 2021
Klaus 1116 East - 11:00 am
Title: Recent Advances on the Maximum Flow Problem
Abstract: 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.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
