Almost-linear-time Weighted ${\ell }_p$-norm Solvers in Slightly Dense Graphs via Sparsification

Deeksha Adil, Brian Bullins, Rasmus Kyng +1

We give almost-linear-time algorithms for constructing sparsifiers with $npoly(\log n)$ edges that approximately preserve weighted $({\ell }_2^2+{\ell }_p^p)$ flow or voltage obj…