The Steiner tree problem is an important combinatorial optimization problem with applications in a wide range of areas, such as very-large-scale integration (VLSI) physical design, the design of virtual private networks, and so on. It is an NP-hard problem and so there has been a good deal of effort to design approximation schemes for it. Of these, the combinatorial algorithm by Robins and Zelikovsky [1] is the best, giving an approximation ratio of 1.55.

The aim of this paper is to give “an LP-based approximation algorithm ... with an improved approximation” ratio, namely, ln(4)+ &egr; < 1.39 for any &egr;. Toward this goal, the paper first presents an LP-relaxation called DCR and a (1+ &egr;) approximate solution. This approximate algorithm is then combined in an iterative randomized rounding technique. Using a lemma called the bridge lemma, it is shown that the expected approximation ratio of this randomized algorithm is ln(4) + &egr; for any &egr;. It is shown how to derandomize this result using the method of limited independence. This leads to a deterministic approximation algorithm with approximation ratio ln(4) + &egr;.

A byproduct of the analysis in this paper is that the integrality gap of the DCR LP is at most 1.55. This answers in the affirmative “a long standing open problem ... whether there is an LP relaxation of [the] Steiner tree [problem] with [an] integrality gap smaller than 2.”