Flows in Almost Linear Time via Adaptive Preconditioning
share
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 ℓ_p-norm minimizing flow for p large (p ∈ [ω(1), o(^2/3 n) ]), and their duals, ℓ_p-norm semi-supervised learning for p close to 1. As p tends to infinity, ℓ_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 ℓ_2 and ℓ_p norm objectives, and decomposing graphs into uniform expanders.
READ FULL TEXT