On the integrality ratio for tree augmentation |
| |
| Authors: | J. Cheriyan, H. Karloff, R. Khandekar,J. K nemann |
| |
| Affiliation: | aDepartment of Comb. & Opt., University of Waterloo, Waterloo ON, Canada N2L 3G1;bAT&T Labs-Research, 180 Park Ave., Florham Park, NJ 07932, USA;cIBM T.J.Watson Research Center, Yorktown Heights, NY 10598, USA |
| |
| Abstract: | We show that the standard linear programming relaxation for the tree augmentation problem in undirected graphs has an integrality ratio that approaches  . 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  . |
| |
| Keywords: | Connectivity augmentation 2-edge-connected graph Linear programming Integer programming Integrality ratio Tree augmentation |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
