- NAVIGATING CENTRAL PATH WIT...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in November 2013
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:
Created by Holly A Jones at Tuesday, October 29, 2013 at 8:53 AM.