Videos

Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs

Presenter
December 5, 2011
Keywords:
  • sparse graphs
  • geometric algorithms
  • graph theory algorithms
  • combinatorial optimization
  • approximation algorithms
  • min-cut max-flow
MSC:
  • 68W25
  • 68W40
  • 68Wxx
  • 05Cxx
  • 05-xx
  • 05C60
  • 05C10
  • 90C47
Abstract
The maximum flow problem and its dual, the minimum s-t cut problem, are two of the most fundamental and extensively studied problems in Operations Research and Optimization. They have many direct applications and are also often used as subroutines in other algorithms. In this talk, I'll describe a new technique for approximating the maximum flow in capacitated, undirected graphs. I'll then show how to use this technique to develop the asymptotically fastest known algorithm for solving this problem. The algorithm will work by treating the graph as a network of resistors and solving a sequence of electrical flow problems with varying resistances on the edges. After describing the algorithm, I'll briefly survey how I think it fits into the broader landscape of spectral graph theory. In particular, I will discuss why I believe that there is a new emerging frontier of algorithmic spectral graph theory that will rely on a broader set of analogies and connections with concepts from geometry. I will explain why I feel that this algorithm and the related questions it motivates serve both as a proof of concept for this agenda and as strong evidence that this theory is still insufficiently understood. Based on joint work with Paul Christiano, Aleksander Madry, Daniel Spielman, and Shanghua Teng.