  In this paper, we introduce a new framework for approximately solving flow
problems in capacitated, undirected graphs and apply it to provide
asymptotically faster algorithms for the maximum $s$-$t$ flow and maximum
concurrent multicommodity flow problems. For graphs with $n$ vertices and $m$
edges, it allows us to find an $\epsilon$-approximate maximum $s$-$t$ flow in
time $O(m^{1+o(1)}\epsilon^{-2})$, improving on the previous best bound of
$\tilde{O}(mn^{1/3} poly(1/\epsilon))$. Applying the same framework in the
multicommodity setting solves a maximum concurrent multicommodity flow problem
with $k$ commodities in $O(m^{1+o(1)}\epsilon^{-2}k^2)$ time, improving on the
existing bound of $\tilde{O}(m^{4/3} poly(k,\epsilon^{-1})$.
  Our algorithms utilize several new technical tools that we believe may be of
independent interest:
  - We give a non-Euclidean generalization of gradient descent and provide
bounds on its performance. Using this, we show how to reduce approximate
maximum flow and maximum concurrent flow to the efficient construction of
oblivious routings with a low competitive ratio.
  - We define and provide an efficient construction of a new type of flow
sparsifier. In addition to providing the standard properties of a cut
sparsifier our construction allows for flows in the sparse graph to be routed
(very efficiently) in the original graph with low congestion.
  - We give the first almost-linear-time construction of an
$O(m^{o(1)})$-competitive oblivious routing scheme. No previous such algorithm
ran in time better than $\tilde{{\Omega}}(mn)$.
  We also note that independently Jonah Sherman produced an almost linear time
algorithm for maximum flow and we thank him for coordinating submissions.

Data Structures and Algorithms