Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Friday, November 1, 2013 - 4:00pm to 5:00pm
Location: 
32-G449 (Patil/Kiva)
Speaker: 
Aleksander Madry, Ecole polytechnique fédérale de Lausanne

Abstract:

We describe a new way of employing electrical flow computations to solve the maximum flow and minimum s-t cut problems. This approach draws on ideas underlying path-following interior-point methods (IPMs) – a powerful tool in convex optimization - and exploits certain interplay between maximum flows and bipartite matchings.

The resulting algorithm provides improvements over some long-standing running time bounds for the maximum flow and minimum s-t cut problems, as well as, the closely related bipartite matching problem. Additionally, we establish a connection between primal-dual structure of electrical flows and convergence behavior of IPMs when applied to flow problems. This connection enables us to overcome the notorious Omega(sqrt(m))-iterations convergence barrier that all the known interior-point methods suffer from.