[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

The University of Chicago Computer Science Department
 
 THEORY SEMINAR REMINDER
 
 Friday, May 30, 2014
3:00 p.m.
Ryerson 251
 
Aleksander Madry
Ecole Polytechnique Federale De Lausanne
thl.epfl.ch/madry/
 
 
Title: “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.
 
 
Hosts: Prof. Janos Simon
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140530/a00bedf1/attachment.htm