Hypergraphic LP relaxations for Steiner trees

DOI10.1007/978-3-642-13036-6_29zbMATH Open1285.90046arXiv0910.0281OpenAlexW1928219016MaRDI QIDQ3569832FDOQ3569832

Authors:

Publication date: 22 June 2010

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

Abstract: We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Koenemann et al. [Math. Programming, 2009]. Specifically, we are interested in proving upper bounds on the integrality gap of this LP, and studying its relation to other linear relaxations. Our results are the following. Structural results: We extend the technique of uncrossing, usually applied to families of sets, to families of partitions. As a consequence we show that any basic feasible solution to the partition LP formulation has sparse support. Although the number of variables could be exponential, the number of positive variables is at most the number of terminals. Relations with other relaxations: We show the equivalence of the partition LP relaxation with other known hypergraphic relaxations. We also show that these hypergraphic relaxations are equivalent to the well studied bidirected cut relaxation, if the instance is quasibipartite. Integrality gap upper bounds: We show an upper bound of sqrt(3) ~ 1.729 on the integrality gap of these hypergraph relaxations in general graphs. In the special case of uniformly quasibipartite instances, we show an improved upper bound of 73/60 ~ 1.216. By our equivalence theorem, the latter result implies an improved upper bound for the bidirected cut relaxation as well.

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

Recommendations

• Hypergraphic LP relaxations for Steiner trees
• New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree

zbMATH Keywords

linear programmingapproximation algorithmhypergraphsnetwork designSteiner tree problemintegrality gapsuncrossing method

Mathematics Subject Classification ID

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

Cited In (14)

• New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
• Chvátal-Gomory cuts for the Steiner tree problem
• Stronger path‐based extended formulation for the Steiner tree problem
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• A comparison of Steiner tree relaxations
• Solving Steiner trees: Recent advances, challenges, and perspectives
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• A partition-based relaxation for Steiner trees
• Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound
• Strong Steiner tree approximations in practice
• A linear programming based approach to the Steiner tree problem with a fixed number of terminals
• Approximating Minimum Cost Connectivity Orientation and Augmentation
• Hypergraphic LP relaxations for Steiner trees
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations

This page was built for publication: Hypergraphic LP relaxations for Steiner trees

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