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

Paul Christiano, Jonathan A. Kelner, Aleksander Madry +2

We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow proble…