The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing

Paul Paschmanns, Vera Traub

The Steiner Tree problem asks for the cheapest way of connecting a given subset of the vertices in an undirected graph. One of the most prominent linear programming relaxations for…