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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we introduce a new framework for approximately solving flowproblems in capacitated, undirected graphs and apply it to provideasymptotically faster algorithms for the maximum $s$-$t$ flow and maximumconcurrent multicommodity flow problems. For graphs with $n$ vertices and $m$edges, it allows us to find an $\epsilon$-approximate maximum $s$-$t$ flow intime $O(m^{1+o(1)}\epsilon^{-2})$, improving on the previous best bound of$\tilde{O}(mn^{1/3} poly(1/\epsilon))$. Applying the same framework in themulticommodity setting solves a maximum concurrent multicommodity flow problemwith $k$ commodities in $O(m^{1+o(1)}\epsilon^{-2}k^2)$ time, improving on theexisting bound of $\tilde{O}(m^{4/3} poly(k,\epsilon^{-1})$.  Our algorithms utilize several new technical tools that we believe may be ofindependent interest:  - We give a non-Euclidean generalization of gradient descent and providebounds on its performance. Using this, we show how to reduce approximatemaximum flow and maximum concurrent flow to the efficient construction ofoblivious routings with a low competitive ratio.  - We define and provide an efficient construction of a new type of flowsparsifier. In addition to providing the standard properties of a cutsparsifier our construction allows for flows in the sparse graph to be routed(very efficiently) in the original graph with low congestion.  - We give the first almost-linear-time construction of an$O(m^{o(1)})$-competitive oblivious routing scheme. No previous such algorithmran in time better than $\tilde{{\Omega}}(mn)$.  We also note that independently Jonah Sherman produced an almost linear timealgorithm for maximum flow and we thank him for coordinating submissions.

An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations