The Bidirected Cut Relaxation for Steiner Tree Has Integrality Gap Smaller than 2
Abstract. 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 is to compute a minimum-weight tree containing all terminals (and possibly further vertices). The best-known approximation algorith...
Jarosław Byrka, Fabrizio Grandoni, Vera Traub
· SIAM Journal on Computing · 0 citations