Name
Abstract | ||
|---|---|---|
We show that the standard linear programming relaxation for the tree augmentation problem in undirected graphs has an integrality ratio that approaches 32. This refutes a conjecture of Cheriyan, Jordan, and Ravi [J. Cheriyan, T. Jordan, 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 43. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.orl.2008.01.009 | Oper. Res. Lett. |
Keywords | DocType | Volume |
tree augmentation,j. cheriyan,linear programming,undirected graph,connectivity augmentation,integer programming,european symposium,tree augmentation.,tree augmentation problem,integrality ratio,longer version,t. jordan,standard linear programming relaxation,2-edge-connected graph,laminar family,connected graph,linear programming relaxation,linear program | Journal | 36 |
Issue | ISSN | Citations |
4 | Operations Research Letters | 14 |
PageRank | References | Authors |
1.00 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Cheriyan | 1 | 283 | 29.24 |
| Howard Karloff | 2 | 1673 | 195.13 |
| R. Khandekar | 3 | 17 | 1.41 |
| Jochen Könemann | 4 | 158 | 9.98 |