Chakrabarty, DeeparnabKönemann, JochenPritchard, David2010-10-042010-10-042010-10-04201010.1016/j.orl.2010.09.004https://infoscience.epfl.ch/handle/20.500.14299/54785WOS:0002844967000171006.2249Recently, 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.HypergraphIntegrality gapRandomized algorithmSteiner treeIntegrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper boundtext::journal::journal article::research article