1.5k citations · 5.7k across the 60 of their papers we have counts for
Showing 2010Show all
3 papers · 1 filter
cs.DS2010★ 1 cited
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…
cs.DS2010★ 14 cited
Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
Aleksander Madry
We present a general method of designing fast approximation algorithms for cut-based minimization problems in undirected graphs. In particular, we develop a technique that given an…
cs.DS2010★ 5 cited
Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms
Aleksander Madry
We combine the work of Garg and Konemann, and Fleischer with ideas from dynamic graph algorithms to obtain faster (1-eps)-approximation schemes for various versions of the multicom…