Summary: In this paper we study the Steiner tree problem in graphs for the case in which vertices as well as edges have weights associated with them. A greedy approximation algorithm based on ‘spider decompositions’ was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of \(2\ln k\), where \(k\) is the number of terminals. However, the best known lower bound on the approximation ratio is \((1-o(1))\ln k\), assuming that \(\text{NP}\nsubseteq \text{DTIME}[{}n^{O(\log\log n)}]{}\), by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of \(\ln k\). For the weighted case we develop a new decomposition theorem and generalize the notion of ‘spiders’ to ‘branch-spiders’ that are used to design a new algorithm with a worst case approximation factor of \(1.5\ln k\). We then generalize the method to yield an approximation factor of \((1.35+\varepsilon)\ln k\), for any constant \(\varepsilon>0\).
These algorithms, although polynomial, are not very practical due to their high running time, since we need to find many minimum weight matchings repeatedly in each iteration. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of \(1.6103\ln k\). The techniques developed for this algorithm imply a method of approximating node weighted network design problems defined by \(0\)-\(1\) proper functions as well.
These new ideas also lead to improved approximation guarantees for the problem of finding a minimum node weighted connected dominating set. The previous best approximation guarantee for this problem was \(3\ln n\) by S. Guha and S. Khuller [Algorithmica 20, No. 4, 374–387 (1998; Zbl 0895.68106)]. By a direct application of the methods developed in this paper we are able to develop an algorithm with an approximation factor of \((1.35+\varepsilon)\ln n\) for any fixed \(\varepsilon>0\).