Jarosław Byrka

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...