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 describe a simple deterministic near-linear time approximation scheme foruncapacitated minimum cost flow in undirected graphs with real edge weights, aproblem also known as transshipment. Specifically, our algorithm takes as inputa (connected) undirected graph $G = (V, E)$, vertex demands $b \in\mathbb{R}^V$ such that $\sum_{v \in V} b(v) = 0$, positive edge costs $c \in\mathbb{R}_{>0}^E$, and a parameter $\varepsilon > 0$. In $O(\varepsilon^{-2} m\log^{O(1)} n)$ time, it returns a flow $f$ such that the net flow out of eachvertex is equal to the vertex's demand and the cost of the flow is within a $(1+ \varepsilon)$ factor of optimal. Our algorithm is combinatorial and has norunning time dependency on the demands or edge costs.  With the exception of a recent result presented at STOC 2022 for polynomiallybounded edge weights, all almost- and near-linear time approximation schemesfor transshipment relied on randomization in two main ways: 1) to embed theproblem instance into low-dimensional space and 2) to randomly pick targetlocations to send flow so nearby opposing demands can be satisfied. Ouralgorithm instead deterministically approximates the cost of routing decisionsthat would be made if the input were subject to a random tree embedding. Toavoid computing the $\Omega(n^2)$ vertex-vertex distances that an approximationof this kind suggests, we also limit the available routing decisions usingdistances explicitly stored in the well-known Thorup-Zwick distance oracle.

A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs