Hypergraphic LP Relaxations for Steiner Trees

DOI10.1007/978-3-642-13036-6_29zbMath1285.90046arXiv0910.0281OpenAlexW1928219016MaRDI 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 programmingapproximation algorithmSteiner tree problemhypergraphsnetwork designintegrality gapsuncrossing method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Hypergraphs (05C65) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound ⋮ Stronger path‐based extended formulation for the Steiner tree problem ⋮ A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Approximating Minimum Cost Connectivity Orientation and Augmentation ⋮ Strong Steiner Tree Approximations in Practice

This page was built for publication: Hypergraphic LP Relaxations for Steiner Trees