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

DOI10.1016/J.ORL.2010.09.004zbMATH Open1227.05203arXiv1006.2249OpenAlexW2042788891MaRDI QIDQ614043FDOQ614043

Authors: Sumit K. Garg 

Publication date: 23 December 2010

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

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.

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

Recommendations

• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• Hypergraphic LP relaxations for Steiner trees
• Hypergraphic LP relaxations for Steiner trees
• 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

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)

Cites Work

• Title not available (Why is that?)
• Tighter Bounds for Graph Steiner Tree Approximation
• An improved LP-based approximation for Steiner tree
• Matroids and the greedy algorithm
• On Steiner trees and minimum spanning trees in hypergraphs
• Hypergraphic LP relaxations for Steiner trees
• Title not available (Why is that?)

Cited In (4)

• 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
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations

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)