Faster <i>p</i>-norm minimizing flows, via smoothed <i>q</i>-norm problems

Abstract

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Faster p-norm minimizing flows, via smoothed q-norm problemsDeeksha Adil and Sushant SachdevaDeeksha Adil and Sushant Sachdevapp.892 - 910Chapter DOI:https://doi.org/10.1137/1.9781611975994.54PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We present faster high-accuracy algorithms for computing ℓp-norm minimizing flows. On a graph with m edges, our algorithm can compute a (1 + 1/poly(m))-approximate unweighted ℓp-norm minimizing flow with operations, for any p ≥ 2, giving the best bound for all p ≳ 5.24. Combined with the algorithm from the work of Adil et al. (SODA '19), we can now compute such flows for any 2 ≤ p ≤ mo(1) in time at most O(m1.24). In comparison, the previous best running time was Ω(m1.33) for large constant p. For p ∼ σ−1 log m, our algorithm computes a (1 + σ)-approximate maximum flow on undirected graphs using m1+o(1)σ−1 operations, matching the current best bound, albeit only for unit-capacity graphs. We also give an algorithm for solving general ℓp-norm regression problems for large p. Our algorithm makes calls to a linear solver. This gives the first high-accuracy algorithm for computing weighted ℓp-norm minimizing flows that runs in time o(m1.5) for some p = mΩ(1). Our key technical contribution is to show that smoothed ℓp-norm problems introduced by Adil et al., are interreducible for different values of p. No such reduction is known for standard ℓp-norm problems. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011

Locations

• arXiv (Cornell University) - View - PDF
• Society for Industrial and Applied Mathematics eBooks - View