On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree

DOI10.1007/s10107-016-0987-5zbMath1360.90221OpenAlexW2276707316MaRDI QIDQ344954

Laura Sanità, Jochen Könemann, Neil Olver, Andreas Emil Feldmann

Publication date: 25 November 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/25096

zbMATH Keywords

Steiner tree problemlinear programming relaxationapproximation algorithmsbidirected cut relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

The last dozen of years of or research in Czechia and Slovakia ⋮ 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 Efficient Approximation Algorithm for the Steiner Tree Problem

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A fast algorithm for Steiner trees
• The Steiner tree problem
• New approximation algorithms for the Steiner tree problems
• On Steiner trees and minimum spanning trees in hypergraphs
• An 11/6-approximation algorithm for the network Steiner problem
• A dual ascent approach for steiner tree problems on a directed graph
• Hypergraphic LP Relaxations for Steiner Trees
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Thek-Steiner Ratio in Graphs
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• Reducibility among Combinatorial Problems
• A catalog of steiner tree formulations
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner Tree Approximation via Iterative Randomized Rounding
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• Optimum branchings
• Steiner Minimal Trees
• Matroids and the greedy algorithm
• A faster approximation algorithm for the Steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs