Loading...
research article
Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound
Recently, Byrka, Grandoni, RothvoBand Sanita gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm. (C) 2010 Elsevier B.V. All rights reserved.
Type
research article
Web of Science ID
WOS:000284496700017
ArXiv ID
1006.2249
Authors
Publication date
2010
Publisher
Published in
Volume
38
Issue
6
Start page
567
End page
570
Peer reviewed
NON-REVIEWED
EPFL units
Available on Infoscience
October 4, 2010
Use this identifier to reference this record