Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
share
Embeddings of graphs into distributions of trees that preserve distances in expectation are a cornerstone of many optimization algorithms. Unfortunately, online or dynamic algorithms which use these embeddings seem inherently randomized and ill-suited against adaptive adversaries. In this paper we provide a new tree embedding which addresses these issues by deterministically embedding a graph into a single tree containing O(log n) copies of each vertex while preserving the connectivity structure of every subgraph and O(log^2 n)-approximating the cost of every subgraph. Using this embedding we obtain several new algorithmic results: We reduce an open question of Alon et al. [SODA 2004] – the existence of a deterministic poly-log-competitive algorithm for online group Steiner tree on a general graph – to its tree case. We give a poly-log-competitive deterministic algorithm for a closely related problem – online partial group Steiner tree – which, roughly, is a bicriteria version of online group Steiner tree. Lastly, we give the first poly-log approximations for demand-robust Steiner forest, group Steiner tree and group Steiner forest.
READ FULL TEXT