View article

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 ∊-approximate maximum s-t flow in time O(m^1+o(1)∊⁻²), improving on the previous best bound of Õ(mn^1/3poly(∊⁻¹)). Applying the same framework in the multicommodity setting solves a maximum concurrent multicommodity flow problem with k commodities in O(m^1+o(1)∊⁻²k²) time, improving on the existing bound of Õ(m^4/3poly(k, ∊⁻¹)).

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 …