ACM Transactions on Algorithms · 2015 · 53 citations · 10 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsEdge ComputingApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsGraph TheoryConnectivity AlgorithmsTree Algorithms
The Tree Augmentation Problem (TAP) is as follows: given a connected graph G =( V , ε ) and an edge set E on V , find a minimum size subset of edges F ⊆ E such that ( V , ε ∪ F ) is 2-edge-connected. In the conference version [Even et al. 2001] was sketched a 1.5-approximation algorithm for the problem. Since a full proof was very complex and long, the journal version was cut into two parts. The first part [Even et al. 2009] only proved ratio 1.8. An attempt to simplify the second part produced an error in Even et al. [2011]. Here we give a correct, different, and self-contained proof of the ratio 1.5 that is also substantially simpler and shorter than the previous proofs.
10
Improved approximation algorithms for network design problems
M. X. Goemans, Andrew V. Goldberg, Serge Plotkin et al. · eCommons (Cornell University) · 1994 · 195 citations · Full text
Approximation Algorithms for Graph Augmentation
Samir Khuller, Ramakrishna Thurimella · Journal of Algorithms · 1993 · 116 citations
Approximation Algorithms for NP-Hard Problems
Ravindran Kannan, Marek Karpiński · Oberwolfach Reports · 2005 · 72 citations