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

Embeddings of graphs into distributions of trees that preserve distances inexpectation are a cornerstone of many optimization algorithms. Unfortunately,online or dynamic algorithms which use these embeddings seem inherentlyrandomized and ill-suited against adaptive adversaries.  In this paper we provide a new tree embedding which addresses these issues bydeterministically embedding a graph into a single tree containing $O(\log n)$copies of each vertex while preserving the connectivity structure of everysubgraph and $O(\log^2 n)$-approximating the cost of every subgraph.  Using this embedding we obtain several new algorithmic results: We reduce anopen question of Alon et al. [SODA 2004] -- the existence of a deterministicpoly-log-competitive algorithm for online group Steiner tree on a general graph-- to its tree case. We give a poly-log-competitive deterministic algorithm fora closely related problem -- online partial group Steiner tree -- which,roughly, is a bicriteria version of online group Steiner tree. Lastly, we givethe first poly-log approximations for demand-robust Steiner forest, groupSteiner tree and group Steiner forest.

Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries