News & Events

Theory of Computation Seminars

Faster Energy Maximization for Faster Maximum Flow

Aaron Sidford, Assistant Professor, Management Science and Engineering, Stanford University

Dec 2, 2019

The maximum flow problem is one of the most well-studied problems in combinatorial optimization. It encompasses a broad 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 present recent advances in obtaining provably faster algorithms for solving the maximum flow problem. In particular, I will show how to solve the maximum flow problem on m-edge n-vertex unit-capacity directed graphs in time almost m^11/8 improving upon the previous best running time of almost m^10/7. Interestingly, this result will stem by considering the interplay between recent advances in interior point methods for solving maximum flow on directed graphs with recent advances in solving classes of undirected flow problems.

This talk reflects joint work with Yang P. Liu (arxiv:1910.14276).


Speaker Bio

Aaron Sidford is an assistant professor of Management Science and Engineering and, by courtesy, of Computer Science at Stanford University. He received his PhD from the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology, where he was advised by Jonathan Kelner. His research interests lie broadly in optimization, the theory of computation, and the design and analysis of algorithms, with an emphasis on work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures.


Carol Harlow