Flows in almost linear time via adaptive preconditioning

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 (log 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. Our framework is inspired by the routing-based solver for Laplacian linear systems by Spielman and Teng (STOC ’04, SIMAX ’14), and is based on several new tools we develop, including adaptive non-linear preconditioning, tree-routings, and (ultra-)sparsification for mixed ℓ 2 and ℓ p norm objectives.

Authors

• Rasmus Kyng
• Richard Peng
• Sushant Sachdeva
• Di Wang 0005

Keywords

• Network flows
• convex optimization
• graph sparsification
• preconditioning