Prof. Dr. Vera Traub, ETH Zürich

The Steiner tree problem is one of the most intensively studied network design problems. It asks to connect a given set of terminals in the cheapest possible way. In talk we will give an introduction to approximation algorithms for Steiner trees and present recent progress in the area. In this context, we will also discuss linear programming relaxations for Steiner tree and their integrality gaps. In particular, we present the recent result that the integrality gap of the bidirected cut relaxation for Steiner tree is strictly below 2.
The bidirected cut relaxation (BCR) is a promising ingredient for the design of fast and accurate approximation algorithms for Steiner tree. It is known to be integral in the special case of spanning tree case [Edmonds'67]. For general instances, however it was not known whether the integrality gap of BCR is better than 2, which is the integrality gap of the natural undirected relaxation. We resolve this question by proving that the integrality gap of BCR ist at most 1.9988 (joint work with Jarek Byrka and Fabrizio Grandoni).