Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
From MaRDI portal
Publication:4575906
DOI10.1137/1.9781611974782.157zbMath1410.68268arXiv1607.03791OpenAlexW4233583517MaRDI QIDQ4575906
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.03791
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (10)
On the tree augmentation problem ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ LP-relaxations for tree augmentation ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ Unnamed Item ⋮ How to Secure Matchings Against Edge Failures ⋮ On small-depth tree augmentations ⋮ Approximation algorithms for connectivity augmentation problems ⋮ 2-node-connectivity network design
This page was built for publication: Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
