Hypergraphic LP Relaxations for Steiner Trees

DOI10.1007/978-3-642-13036-6_29zbMath1285.90046arXiv0910.0281MaRDI QIDQ3569832

No author found.

Publication date: 22 June 2010

Published in: SIAM Journal on Discrete Mathematics, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

linear programming; approximation algorithm; Steiner tree problem; hypergraphs; network design; integrality gaps; uncrossing method

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C05: Linear programming

05C65: Hypergraphs

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)