Name
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 ℓ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.
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.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3313276.3316410 | Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |
Keywords | DocType | Volume |
Network flows, convex optimization, graph sparsification, preconditioning | Journal | abs/1906.10340 |
ISSN | ISBN | Citations |
0737-8017 | 978-1-4503-6705-9 | 2 |
PageRank | References | Authors |
0.38 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rasmus Kyng | 1 | 56 | 9.00 |
| Richard Peng | 2 | 522 | 42.64 |
| Sushant Sachdeva | 3 | 171 | 16.90 |
| Di Wang | 4 | 19 | 3.79 |