Nearly Maximum Flows in Nearly Linear Time

Beyond the flow decomposition barrier

Andrew V. Goldberg and Satish Rao · 1998

Earlier work this paper cites.

Finding maximum flows in undirected graphs seems easier than bipartite matching

David R. Karger and Matthew S. Levine · 1998

Earlier work this paper cites.

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Tom Leighton and Satish Rao · 1999

Earlier work this paper cites.

Randomized approximation schemes for cuts and flows in capacitated graphs

András A. Benczúr and David R. Karger · 2002

Earlier work this paper cites.

A practical algorithm for constructing oblivious routing schemes

Marcin Bienkowski, Miroslaw Korzeniowski, and Harald Räcke · 2003

Cited alongside, same era.

A polynomial-time tree decomposition to minimize congestion

Chris Harrelson, Kirsten Hildrum, and Satish Rao · 2003

Cited alongside, same era.

Smooth minimization of non-smooth functions

Yu Nesterov · 2005

Cited alongside, same era.

Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems

Original

Daniel A. Spielman and Shang-Hua Teng · 2006

Cited alongside, same era.

Fast approximation algorithms for cut-based problems in undirected graphs

Aleksander Madry · 2010

Later among the works it cites.

Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng · 2011

Later among the works it cites.

A fast solver for a class of linear systems

Ioannis Koutis, Gary L. Miller, and Richard Peng · 2012

Later among the works it cites.

A simple, combinatorial algorithm for solving sdd systems in nearly-linear time

Original

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013

Closest in time.