Faster p-norm minimizing flows, via smoothed q-norm problems

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 pm 1+ 1 p-1 +o(1) 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 ≤ m o(1) in time at most O(m 1.24 ). In comparison, the previous best running time was Ω(m 1.33 ) for large constant p. For p ∼ δ -1 log m, our algorithm computes a (1+δ)-approximate maximum flow on undirected graphs using m 1+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 pm 1 3 +o(1) log 2 (1/ε) calls to a linear solver. This gives the first high-accuracy algorithm for computing weighted ℓ p -norm minimizing flows that runs in time o(m 1.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.