Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings
Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings
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(log2 n)-approximating the cost of every subgraph. Using this embedding we obtain the first deterministic bicriteria approximation algorithm for the online covering Steiner problem as well as the first poly-log approximations for demand-robust Steiner forest, group Steiner tree and group Steiner forest.
Leibniz International Proceedings in Informatics (LIPIcs), 244
30th Annual European Symposium on Algorithms (ESA 2022)
ISBN:978-3-95977-247-1
ISSN:1868-8969
- ETH Zurich Switzerland
- Carnegie Mellon University United States
- Leibniz Association Germany
- Schloss Dagstuhl – Leibniz Center for Informatics Germany
Mathematics of computing → Approximation algorithms, metric embeddings, 000, Theory of computation → Random projections and metric embeddings, online algorithms, Tree metrics, deterministic algorithm, group Steiner tree, Tree Metrics, 004, Tree Metrics; metric embeddings; approximation algorithms; group Steiner forest; group Steiner tree; demand-robust algorithms; online algorithms; deterministic algorithm, group Steiner forest, demand-robust algorithms, Mathematics of computing → Paths and connectivity problems, approximation algorithms, Mathematics of computing → Trees, deterministic algorithms, ddc: ddc:004
Mathematics of computing → Approximation algorithms, metric embeddings, 000, Theory of computation → Random projections and metric embeddings, online algorithms, Tree metrics, deterministic algorithm, group Steiner tree, Tree Metrics, 004, Tree Metrics; metric embeddings; approximation algorithms; group Steiner forest; group Steiner tree; demand-robust algorithms; online algorithms; deterministic algorithm, group Steiner forest, demand-robust algorithms, Mathematics of computing → Paths and connectivity problems, approximation algorithms, Mathematics of computing → Trees, deterministic algorithms, ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!