# Almost-linear-time Weighted ℓp-norm Solvers in Slightly Dense Graphs via Sparsification

arXiv: https://arxiv.org/abs/2102.06977 · HTML: https://mlsanity.com/paper/2102.06977/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2021.

## Built on by (most cited first, 1 of 1)

- [ℓ2-norm Flow Diffusion in Near-Linear Time](https://mlsanity.com/paper/2105.14629/) (2021)

## Abstract (arXiv)

We give almost-linear-time algorithms for constructing sparsifiers with n poly(log n) edges that approximately preserve weighted (ℓ22 + ℓpp) flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier construction for such mixed objectives beyond unit ℓp weights, and is based on expander decompositions. For voltage objectives, we give the first sparsifier construction for these objectives, which we build using graph spanners and leverage score sampling. Together with the iterative refinement framework of [Adil et al, SODA 2019], and a new multiplicative-weights based constant-approximation algorithm for mixed-objective flows or voltages, we show how to find (1+2-poly(log n)) approximations for weighted ℓp-norm minimizing flows or voltages in p(m1+o(1) + n4/3 + o(1)) time for p=ω(1), which is almost-linear for graphs that are slightly dense (m ≥ n4/3 + o(1)).