Compression for data archiving and backup revisited
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
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.
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
Imran Nasim, Michael E. Henderson
Mathematics
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998