Flows in Almost Linear Time via Adaptive Preconditioning

Abstract

We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to $(1+1/poly(n))$ accuracy in almost-linear time. These problems include ${\ell }_p$-norm minimizing flow for $p$ large ($p\in [\ddot{I}‰(1),o({\log }^{2/3}n)]$), and their duals, ${\ell }_p$-norm semi-supervised learning for $p$ close to $1$. As $p$ tends to infinity, ${\ell }_p$-norm flow and its dual tend to max-flow and min-cut respectively. Using this connection and our algorithms, we give an alternate approach for approximating undirected max-flow, and the first almost-linear time approximations of discretizations of total variation minimization objectives. This algorithm demonstrates that many tools previous viewed as limited to linear systems are in fact applicable to a much wider range of convex objectives. It is based on the the routing-based solver for Laplacian linear systems by Spielman and Teng (STOC '04, SIMAX '14), but require several new tools: adaptive non-linear preconditioning, tree-routing based ultra-sparsification for mixed ${\ell }_2$ and ${\ell }_p$ norm objectives, and decomposing graphs into uniform expanders.