English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give almost-linear-time algorithms for constructing sparsifiers with npoly(log n) edges that approximately preserve weighted (l2 + l p p) flow or voltage objectives on graphs. For flow objectives, this is the first sparsifier construction for such mixed objectives beyond unit lp 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 ) approximations for weighted lp-norm minimizing flows or voltages in p(m +n) time for p = ω(1), which is almost-linear for graphs that are slightly dense (m ≥ n). University of Toronto, TTI Chicago, ETH Zurich. E-mail addresses: {deeksha|sachdeva}@cs.toronto.edu, bbullins@ttic.edu, kyng@inf.ethz.ch.

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