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 give the first non-trivial fully dynamic probabilistic tree embeddingalgorithm for weighted graphs undergoing edge insertions and deletions. Weobtain a trade-off between amortized update time and expected stretch againstan oblivious adversary. At the two extremes of this trade-off, we can maintaina tree of expected stretch $ O (\log^4 n) $ with update time $ m^{1/2 + o(1)} $or a tree of expected stretch $ n^{o(1)} $ with update time $ n^{o(1)} $ (foredge weights polynomial in $ n $). A guarantee of the latter type has so faronly been known for maintaining tree embeddings with average (instead ofexpected) stretch [Chechik/Zhang, SODA '20].  Our main result has direct implications to fully dynamic approximate distanceoracles and fully dynamic buy-at-bulk network design. For dynamic distanceoracles, our result is the first to break the $ O (\sqrt{m}) $ update-timebarrier. For buy-at-bulk network design, a problem which also in the staticsetting heavily relies on probabilistic tree embeddings, we give the firstnon-trivial dynamic algorithm. As probabilistic tree embeddings are animportant tool in static approximation algorithms, further applications of ourresult in dynamic approximation algorithms are conceivable.  From a technical perspective, we obtain our main result by first designing adecremental algorithm for probabilistic low-diameter decompositions via acareful combination of Bartal's ball-growing approach [FOCS '96] with thepruning framework of Chechik and Zhang [SODA '20]. We then extend this to afully dynamic algorithm by enriching a well-known 'decremental to fullydynamic' reduction with a new bootstrapping idea to recursively employ a fullydynamic algorithm instead of a static one in this reduction.

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications