  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
algorithms for Steiner tree involve enumeration of a (polynomial but) very
large number of candidate components and are therefore slow in practice.
  A promising ingredient for the design of fast and accurate approximation
algorithms for Steiner tree is the bidirected cut relaxation (BCR): bidirect
all edges, choose an arbitrary terminal as a root, and enforce that each cut
containing some terminal but not the root has one unit of fractional edges
leaving it. BCR is known to be integral in the spanning tree case [Edmonds'67],
i.e., when all the vertices are terminals. For general instances, however, it
was not even known whether the integrality gap of BCR is better than the
integrality gap of the natural undirected relaxation, which is exactly 2. We
resolve this question by proving an upper bound of 1.9988 on the integrality
gap of BCR.
