# Flows in Almost Linear Time via Adaptive Preconditioning

Preprint · Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang

- Archive id: arxiv:1906.10340
- Published: 2019-06-25
- arXiv: https://arxiv.org/abs/1906.10340
- Source URL: https://arxiv.org/abs/1906.10340
- PDF: https://arxiv.org/pdf/1906.10340
- Provenance: arxiv

## 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 \[ω(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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.