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 present a method for solving the transshipment problem - also known asuncapacitated minimum cost flow - up to a multiplicative error of $1 +\varepsilon$ in undirected graphs with non-negative edge weights using atailored gradient descent algorithm. Using $\tilde{O}(\cdot)$ to hidepolylogarithmic factors in $n$ (the number of nodes in the graph), our gradientdescent algorithm takes $\tilde O(\varepsilon^{-2})$ iterations, and in eachiteration it solves an instance of the transshipment problem up to amultiplicative error of $\operatorname{polylog} n$. In particular, this allowsus to perform a single iteration by computing a solution on a sparse spanner oflogarithmic stretch. Using a randomized rounding scheme, we can further extendthe method to finding approximate solutions for the single-source shortestpaths (SSSP) problem. As a consequence, we improve upon prior work by obtainingthe following results: (1) Broadcast CONGEST model: $(1 +\varepsilon)$-approximate SSSP using $\tilde{O}((\sqrt{n} +D)\varepsilon^{-3})$ rounds, where $ D $ is the (hop) diameter of the network.(2) Broadcast congested clique model: $(1 + \varepsilon)$-approximatetransshipment and SSSP using $\tilde{O}(\varepsilon^{-2})$ rounds. (3)Multipass streaming model: $(1 + \varepsilon)$-approximate transshipment andSSSP using $\tilde{O}(n)$ space and $\tilde{O}(\varepsilon^{-2})$ passes. Thepreviously fastest SSSP algorithms for these models leverage sparse hop sets.We bypass the hop set construction; computing a spanner is sufficient with ourmethod. The above bounds assume non-negative edge weights that are polynomiallybounded in $n$; for general non-negative weights, running times scale with thelogarithm of the maximum ratio between non-zero weights.

Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models