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

DOI10.1016/J.ORL.2010.09.004MaRDI QIDQ614043zbMATH OpenOpenAlexFDO

Authors Sumit K. Garg

Publication date 23 December 2010

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.2249

zbMATH Keywords

randomized algorithmhypergraphintegrality gapSteiner tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Integer programming (90C10) Hypergraphs (05C65)

Abstract: Recently Byrka, Grandoni, Rothvoss and Sanita (at STOC 2010) 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.

Recommendations

• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• Near optimal bounds for Steiner trees in the hypercube
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
• Tighter Bounds for Graph Steiner Tree Approximation
• On the integrality gap of the prize-collecting Steiner forest LP
• The Steiner tree problem on graphs: inapproximability results

Cites work

• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 1163724 (Why is no real title available?)
• An improved LP-based approximation for Steiner tree
• Matroids and the greedy algorithm
• On Steiner trees and minimum spanning trees in hypergraphs
• Tighter Bounds for Graph Steiner Tree Approximation

Cited in

(4)

• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• Strong Steiner tree approximations in practice

This page was built for publication: Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q614043)