Theory Seminar - Coordinate Descent Methods for Faster Maximum Flow

Abstract: 

The maximum flow problem is one of the most fundamental and well-studied problems in continuous and combinatorial optimization. Over the past 5 years there have been a series of results which showed how to careful combine new combinatorial graph decompositions with new iterative continuous optimization methods to approximately solve the problem on undirected graphs in nearly linear time. In this talk I will survey this work and show how to develop simple coordinate descent based methods that match the state-of-the-art and in various settings improve upon it. Moreover, I will discuss how this yields an alternative to the recent breakthrough result of Sherman (2017) for solving  ℓ∞-regression and leads to faster exact maximum flow algorithms in various settings.

This talk is based on joint work with Kevin Tian available on arXiv.