| Article ID: | iaor20102857 |
| Volume: | 36 |
| Issue: | 4 |
| Start Page Number: | 399 |
| End Page Number: | 401 |
| Publication Date: | Jul 2008 |
| Journal: | Operations Research Letters |
| Authors: | Cheriyan J, Karloff H, Khandekar R, Knemann J |
We show that the standard linear programming relaxation for the tree augmentation problem in undirected graphs has an integrality ratio that approaches 3/2. This refutes a conjecture of Cheriyan, Jordán, and Ravi (1999) that the integrality ratio is 4/3.