- Conference Paper
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/3n) ]), 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. Show more
Book titleProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
Pages / Article No.
SubjectNetwork flows; convex optimization; graph sparsification; precon-ditioning
Organisational unit09687 - Kyng, Rasmus / Kyng, Rasmus
MoreShow all metadata