The Steiner tree problem is one of the most fundamental NP-hard problems:

given a weighted undirected graph G=(V,E) and a subset of terminal nodes,  find a minimum weight tree spanning the terminals.

In this talk, we introduce a directed LP relaxation and describe an  approximation algorithm based on iterative randomized rounding of a fractional solution.

We prove an approximation guarantee of 1.39 for the algorithm (improving over the previously best known factor of 1.55) and show that the mentioned LP has an integrality gap of at most 1.55 (improving over the previously best known factor of 2).