Article ID Journal Published Year Pages File Type
1142889 Operations Research Letters 2010 4 Pages PDF
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
, , ,