Fall 2014

Electrical Flows, Optimization, and New Approaches to the Maximum Flow Problem III: Maximum Flows and Interior-point Methods

Friday, Aug. 29, 2014 2:00 pm3:00 pm PDT

Add to Calendar


Calvin Lab Auditorium

Graphs are ubiquitous in all modern sciences. This motivates a need for algorithmic tools that are capable of analyzing and computing on graphs in an efficient manner. A need that is even more pressing now that the graphs we are dealing with tend to be massive, rendering traditional methods no longer adequate. 

In this talk, I will discuss a recent progress on the maximum flow problem and use it as an illustration of a broader emerging theme in graph algorithms that employs optimization methods as an algorithmic bridge between our combinatorial and spectral understanding of graphs. 

I will also briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives - most notably, interior-point methods.

The first session of this talk will take place on Thursday, August 28 from 3:30 pm – 4:30 pm; the second session of this talk will take place on Friday, August 29 from 10:00 am – 11:00 am.