Approximating the weight of shallow Steiner trees

This paper deals with the problem of constructing Steiner trees of minimum weight with diameter bounded by d, spanning a given set of v vertices in a graph. Exact solutions or logarithmic ratio approximation algorithms were known before for the cases of d ⩽ 5. Here we give a polynomial-time approximation algorithm of ratio O(log v) for constant d, which is asymptotically optimal unless P = NP, and an algorithm of ratio O(v), for any fixed 0 < ε < 1, for general d.