Showing 2024Show all
2 papers · 1 filter
cs.DS2024
On the Bidirected Cut Relaxation for Steiner Forest
Jarosław Byrka, Fabrizio Grandoni, Vera Traub
The Steiner Forest problem is an important generalization of the Steiner Tree problem. We are given an undirected graph with nonnegative edge costs and a collection of pairs of ver…
cs.DS2024
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
Jarosław Byrka, Fabrizio Grandoni, Vera Traub
The Steiner tree problem is one of the most prominent problems in network design. Given an edge-weighted undirected graph and a subset of the vertices, called terminals, the task i…