Adaptive-adversary-robust algorithms via small copy tree embeddings

DOI10.4230/LIPICS.ESA.2022.63MaRDI QIDQ6969619zbMATH OpenFDO

Authors Bernhard Haepler, D. Ellis Hershkowitz, Goran Zuzic

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.63

zbMATH Keywords

approximation algorithmsdemand-robust algorithmsdeterministic algorithmsgroup Steiner forestgroup Steiner treemetric embeddingsonline algorithmstree metrics

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A general approach to online network optimization problems
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics
• Algorithms – ESA 2004
• Approximating a finite metric by a small number of tree metrics
• Approximation algorithms for the covering Steiner problem
• Better Algorithms for Unfair Metrical Task Systems and Applications
• Dynamic Steiner Tree Problem
• scientific article; zbMATH DE number 5899242 (Why is no real title available?)
• scientific article; zbMATH DE number 5485491 (Why is no real title available?)
• scientific article; zbMATH DE number 2079366 (Why is no real title available?)
• scientific article; zbMATH DE number 1559591 (Why is no real title available?)
• scientific article; zbMATH DE number 7650071 (Why is no real title available?)
• Oblivious network design
• On network design problems: fixed cost flows and the covering Steiner problem
• On the approximability of robust spanning tree problems
• On the Facility Location Problem in Online and Dynamic Models.
• Online node-weighted Steiner tree and related problems
• Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems
• Permutation Strikes Back: The Power of Recourse in Online Metric Matching
• Reordering buffers with logarithmic diameter dependency for trees
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Robust Combinatorial Optimization with Exponential Scenarios
• Thresholded Covering Algorithms for Robust and Max-min Optimization
• Tree embeddings for hop-constrained network design
• Two-Stage Robust Network Design with Exponential Scenarios
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

This page was built for publication: Adaptive-adversary-robust algorithms via small copy tree embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969619)