Almost-linear-time Weighted $\ell_p$-norm Solvers in Slightly Dense Graphs via Sparsification
We give almost-linear-time algorithms for constructing sparsifiers with $n\ poly(\log n)$ edges that approximately preserve weighted $(\ell^{2}_2 + \ell^{p}_p)$ flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier construction for such mixed objectives beyond unit...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2102.06977 http://arxiv.org/abs/2102.06977 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|