Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound
Chakrabarty, Deeparnab; Könemann, Jochen; Pritchard, David
2010

Abstract

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.

Details

Title Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound
Author(s) Chakrabarty, Deeparnab ; Könemann, Jochen ; Pritchard, David
Published in Operations Research Letters
Volume 38
Issue 6
Pages 567-570
Date 2010
Publisher Elsevier
ISSN 0167-6377
Keywords
DOI https://doi.org/10.1016/j.orl.2010.09.004
Other identifier(s) View record in Web of Science
View record in ArXiv
Laboratories DISOPT
Record Appears in Scientific production and competences > SB - School of Basic Sciences > MATH - Institute of Mathematics > DISOPT - Chair of Discrete Optimization
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Work produced at EPFL
Journal Articles
Published
Record creation date 2010-10-04