Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142889 | Operations Research Letters | 2010 | 4 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Deeparnab Chakrabarty, Jochen Könemann, David Pritchard,