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 provide an algorithm which, with high probability, maintains a$(1-\epsilon)$-approximate maximum flow on an undirected graph undergoing$m$-edge additions in amortized $m^{o(1)} \epsilon^{-3}$ time per update. Toobtain this result, we provide a more general algorithm that solves what wecall the incremental, thresholded $p$-norm flow problem that asks to determinethe first edge-insertion in an undirected graph that causes the minimum$\ell_p$-norm flow to decrease below a given threshold in value. Since we solvethis thresholded problem, our data structure succeeds against an adaptiveadversary that can only see the data structure's output. Furthermore, since ouralgorithm holds for $p = 2$, we obtain improved algorithms for dynamicallymaintaining the effective resistance between a pair of vertices in anundirected graph undergoing edge insertions.  Our algorithm builds upon previous dynamic algorithms for approximatelysolving the minimum-ratio cycle problem that underlie previous advances on themaximum flow problem [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS '22]as well as recent dynamic maximum flow algorithms [v.d.Brand-Liu-Sidford, STOC'23]. Instead of using interior point methods, which were a key component ofthese recent advances, our algorithm uses an optimization method based on$\ell_p$-norm iterative refinement and the multiplicative weight update method.This ensures a monotonicity property in the minimum-ratio cycle subproblemsthat allows us to apply known data structures and bypass issues arising fromadaptive queries.

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time