2019/06/25 by Kyng, Rasmus, Peng, Richard, Sachdeva, Sushant +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1906.10340
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(log2/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.