NAVIGATING CENTRAL PATH WITH ELECTRICAL FLOWS: FROM FLOWS TO MATCHINGS, AND BACK

Speaker: Aleksander Madry , É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

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Dana Moshkovitz and Costis Daskalakis

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/420

Speaker URL: None

Speaker Photo:
None

Reminders to: toc@csail.mit.edu

Reminder Subject: TALK: NAVIGATING CENTRAL PATH WITH ELECTRICAL FLOWS: FROM FLOWS TO MATCHINGS, AND BACK

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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2013.

Created by Holly A Jones at Tuesday, October 29, 2013 at 8:53 AM.