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

DOI10.1016/j.orl.2010.09.004zbMath1227.05203arXiv1006.2249OpenAlexW2042788891MaRDI QIDQ614043

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

hypergraphrandomized algorithmSteiner treeintegrality gap

Mathematics Subject Classification ID

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

Related Items (2)

On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Strong Steiner Tree Approximations in Practice

Cites Work

• On Steiner trees and minimum spanning trees in hypergraphs
• An improved LP-based approximation for steiner tree
• Hypergraphic LP Relaxations for Steiner Trees
• Tighter Bounds for Graph Steiner Tree Approximation
• Matroids and the greedy algorithm
• Unnamed Item
• Unnamed Item

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