A Better-Than-2 Approximation for Weighted Tree Augmentation
Authors:
- 1 February 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-12
Abstract
We present an approximation algorithm for Weighted Tree Augmentation with approximation factor 1 + $\ln 2+\varepsilon < 1.7$ . This is the first algorithm beating the longstanding factor of 2, which can be achieved through many standard techniques. −
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- A-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radiusTheoretical Computer Science, 2013
- A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2ACM Transactions on Algorithms, 2009
- On the integrality ratio for tree augmentationOperations Research Letters, 2008
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning treeDiscrete Applied Mathematics, 2003
- Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning SubgraphSIAM Journal on Discrete Mathematics, 2001
- A General Approximation Technique for Constrained Forest ProblemsSIAM Journal on Computing, 1995
- Biconnectivity approximations and graph carvingsJournal of the ACM, 1994
- Approximation Algorithms for Graph AugmentationJournal of Algorithms, 1993
- An application of submodular flowsLinear Algebra and its Applications, 1989
- Approximation Algorithms for Several Graph Augmentation ProblemsSIAM Journal on Computing, 1981