ARC Colloquium: Aaron Sidford (Stanford)

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.

----------------------------------

Speaker's Webpage

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

Event Details

Date/Time:

  • Monday, October 4, 2021
    11:00 am - 12:00 pm
Location: Klaus 1116 East