Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound

Recently, Byrka, Grandoni, Rothvoß and Sanità 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...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 2010-11, Vol.38 (6), p.567-570
Main Authors: Chakrabarty, Deeparnab, Könemann, Jochen, Pritchard, David
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Approximation
Exact sciences and technology
Flows in networks. Combinatorial problems
Hypergraph
Integrality gap
Linear programming
Mathematical analysis
Mathematical programming
Operational research and scientific management
Operational research. Management science
Operations research
Proving
Randomized algorithm
Steiner tree
Trees
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recently, Byrka, Grandoni, Rothvoß and Sanità 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.
ISSN:0167-6377
1872-7468
DOI:10.1016/j.orl.2010.09.004