NAVIGATING CENTRAL PATH WITH ELECTRICAL FLOWS: FROM FLOWS TO MATCHINGS, AND BACK
, École Polytechnique Fédérale de Lausanne (EPFL)
Date: Friday, November 01, 2013
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Dana Moshkovitz and Costis Daskalakis
Contact: Holly A Jones, email@example.com
Relevant URL: http://toc.csail.mit.edu/node/420
Speaker URL: None
TALK: NAVIGATING CENTRAL PATH WITH ELECTRICAL FLOWS: FROM FLOWS TO MATCHINGS, AND BACK
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.
Created by Holly A Jones at Tuesday, October 29, 2013 at 8:53 AM.