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.


Published in:
Operations Research Letters
Year:
2010
Publisher:
Elsevier
ISSN:
0167-6377
Keywords:
Laboratories:




 Record created 2010-10-04, last modified 2018-12-03

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)