Tight bounds for online weighted tree augmentation
type: Item
instance of: scholarly article
title: Tight bounds for online weighted tree augmentation
author: Seeun William Umboh
author: David P. Williamson
author: Joseph (Seffi) Naor
published in: Algorithmica
publication date: 2022-03-25T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10664/
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7498361
MaRDI profile type: Publication
OpenAlex ID: W3216837767
cites work: The Online Set Cover Problem
cites work: On-line generalized Steiner problem
cites work: Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
cites work: Q4527000
cites work: Q5002841
cites work: Hitting sets online and unique-MAX coloring
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: Q3328583
cites work: Improved approximation for tree augmentation: saving by rewiring
cites work: Online and Stochastic Survivable Network Design
cites work: Online Node-weighted Steiner Forest and Extensions via Disk Paintings
cites work: Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems
cites work: Dynamic Steiner Tree Problem
cites work: Q4821529
cites work: Online Node-Weighted Steiner Tree and Related Problems
cites work: Tight Bounds for Online Weighted Tree Augmentation
cites work: Online constrained forest and prize-collecting network design
cites work: A data structure for dynamic trees
cites work: Online Network Design Algorithms via Hierarchical Decompositions
DOI: 10.1007/S00453-021-00888-7
description: scientific article; zbMATH DE number 7498361