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

We present a general framework of designing efficient dynamic approximatealgorithms for optimization on undirected graphs. In particular, we develop atechnique that, given any problem that admits a certain notion of vertexsparsifiers, gives data structures that maintain approximate solutions insub-linear update and query time. We illustrate the applicability of ourparadigm to the following problems.  (1) A fully-dynamic algorithm that approximates all-pairmaximum-flows/minimum-cuts up to a nearly logarithmic factor in$\tilde{O}(n^{2/3})$ amortized time against an oblivious adversary, and$\tilde{O}(m^{3/4})$ time against an adaptive adversary.  (2) An incremental data structure that maintains $O(1)$-approximate shortestpath in $n^{o(1)}$ time per operation, as well as fully dynamic approximateall-pair shortest path and transshipment in $\tilde{O}(n^{2/3+o(1)})$ amortizedtime per operation.  (3) A fully-dynamic algorithm that approximates all-pair effective resistanceup to an $(1+\epsilon)$ factor in $\tilde{O}(n^{2/3+o(1)} \epsilon^{-O(1)})$amortized update time per operation.  The key tool behind result (1) is the dynamic maintenance of an algorithmicconstruction due to Madry [FOCS' 10], which partitions a graph into acollection of simpler graph structures (known as j-trees) and approximatelycaptures the cut-flow and metric structure of the graph. The$O(1)$-approximation guarantee of (2) is by adapting the distance oracles by[Thorup-Zwick JACM `05]. Result (3) is obtained by invoking the random-walkbased spectral vertex sparsifier by [Durfee et al. STOC `19] in a hierarchicalmanner, while carefully keeping track of the recourse among levels in thehierarchy.

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers