License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.9
URN: urn:nbn:de:0030-drops-140782
Go to the corresponding LIPIcs Volume Portal

Adil, Deeksha ; Bullins, Brian ; Kyng, Rasmus ; Sachdeva, Sushant

Almost-Linear-Time Weighted 𝓁_p-Norm Solvers in Slightly Dense Graphs via Sparsification

LIPIcs-ICALP-2021-9.pdf (0.8 MB)


We give almost-linear-time algorithms for constructing sparsifiers with n poly(log n) edges that approximately preserve weighted (𝓁²₂ + 𝓁^p_p) 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(m^{1+o(1)} + n^{4/3 + o(1)}) time for p = ω(1), which is almost-linear for graphs that are slightly dense (m ≥ n^{4/3 + o(1)}).

BibTeX - Entry

  author =	{Adil, Deeksha and Bullins, Brian and Kyng, Rasmus and Sachdeva, Sushant},
  title =	{{Almost-Linear-Time Weighted 𝓁\underlinep-Norm Solvers in Slightly Dense Graphs via Sparsification}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-140782},
  doi =		{10.4230/LIPIcs.ICALP.2021.9},
  annote =	{Keywords: Weighted 𝓁\underlinep-norm, Sparsification, Spanners, Iterative Refinement}

Keywords: Weighted 𝓁_p-norm, Sparsification, Spanners, Iterative Refinement
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI