Publication

Operations Research Letters

Paper

# On the integrality ratio for tree augmentation

## Abstract

We show that the standard linear programming relaxation for the tree augmentation problem in undirected graphs has an integrality ratio that approaches frac(3, 2). This refutes a conjecture of Cheriyan, Jordán, and Ravi [J. Cheriyan, T. Jordán, R. Ravi, On 2-coverings and 2-packings of laminar families, in: Proceedings, European Symposium on Algorithms, 1999, pp. 510-520. A longer version is on the web: http://www.math.uwaterloo.ca/jcheriyan/publications.html] that the integrality ratio is frac(4, 3). Crown Copyright © 2008.