Tight bounds for online weighted tree augmentation

DOI10.1007/s00453-021-00888-7OpenAlexW3216837767MaRDI QIDQ832514

David P. Williamson, Seeun William Umboh, Joseph (Seffi) Naor

Publication date: 25 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10664/

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hitting sets online and unique-MAX coloring
• Online constrained forest and prize-collecting network design
• A data structure for dynamic trees
• On-line generalized Steiner problem
• The Online Set Cover Problem
• Approximation Algorithms for Several Graph Augmentation Problems
• Dynamic Steiner Tree Problem
• Online and Stochastic Survivable Network Design
• Tight Bounds for Online Weighted Tree Augmentation
• Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
• Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems
• Improved approximation for tree augmentation: saving by rewiring
• Online Network Design Algorithms via Hierarchical Decompositions
• Online Node-Weighted Steiner Tree and Related Problems
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings

This page was built for publication: Tight bounds for online weighted tree augmentation