Stronger path‐based extended formulation for the Steiner tree problem
From MaRDI portal
Publication:6068530
DOI10.1002/net.21901OpenAlexW2950605182WikidataQ127655226 ScholiaQ127655226MaRDI QIDQ6068530
Bartosz Filipecki, Mathieu Van Vyve
Publication date: 13 November 2023
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.21901
mixed integer linear programminglinear programming relaxationSteiner treeintegrality gapextended formulationflow-based formulation
Related Items
Optimal Steiner trees under node and edge privacy conflicts ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives
Cites Work
- Unnamed Item
- Unnamed Item
- On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
- A partition-based relaxation for Steiner trees
- The Steiner tree problem
- Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
- Thinning out Steiner trees: a node-based model for uniform edge costs
- SCIP-Jack -- a solver for STP and variants with parallelization extensions
- Swap-vertex based neighborhood for Steiner tree problems
- On Steiner trees and minimum spanning trees in hypergraphs
- The multi-weighted Steiner tree problem: A reformulation by intersection
- A dual ascent approach for steiner tree problems on a directed graph
- Hypergraphic LP Relaxations for Steiner Trees
- Thek-Steiner Ratio in Graphs
- 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
- Matroids and the greedy algorithm
- A comparison of Steiner tree relaxations
