Tight Bounds for Online Weighted Tree Augmentation

DOI10.4230/LIPIcs.ICALP.2019.88OpenAlexW2964541980MaRDI QIDQ5091248

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

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1904.11777

zbMATH Keywords

competitive analysisonline algorithmsnetwork designtree augmentation

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

Tight bounds for online weighted tree augmentation

Cites Work

• 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
• 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

This page was built for publication: Tight Bounds for Online Weighted Tree Augmentation