Compression scheme for digital cinema application
Ligang Lu, Jack L. Kouloheris
IS&T/SPIE Electronic Imaging 2002
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.
Ligang Lu, Jack L. Kouloheris
IS&T/SPIE Electronic Imaging 2002
Igor Devetak, Andreas Winter
ISIT 2003
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Karthik Visweswariah, Sanjeev Kulkarni, et al.
IEEE International Symposium on Information Theory - Proceedings