Matroids and integrality gaps for hypergraphic steiner tree relaxations

DOI10.1145/2213977.2214081zbMath1286.05024arXiv1111.7280OpenAlexW2122195804MaRDI QIDQ5415542

Rico Zenklusen, Thomas Rothvoß, Michel X. Goemans, Neil Olver

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

matroidsapproximation algorithmslinear programming relaxationsintegrality gaps

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (26)

A robust and scalable algorithm for the Steiner problem in graphs ⋮ The Influence of Preprocessing on Steiner Tree Approximations ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Approximating activation edge-cover and facility location problems ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ New approaches to multi-objective optimization ⋮ 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 ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Combination algorithms for Steiner tree variants ⋮ Network design with a discrete set of traffic matrices ⋮ Strong Steiner Tree Approximations in Practice ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Covering problems in edge- and node-weighted graphs ⋮ Computing a tree having a small vertex cover ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Unnamed Item ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Improved approximation algorithms for minimum power covering problems ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Two-level hub Steiner trees ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

This page was built for publication: Matroids and integrality gaps for hypergraphic steiner tree relaxations