@article {15229,
title = {Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets},
journal = {Information and Computation},
volume = {150},
year = {1999},
month = {1999/04/10/},
pages = {57 - 74},
abstract = {In this paper we study the Steiner tree problem in graphs for the case when vertices as well as edges have weights associated with them. A greedy approximation algorithm based on {\textquotedblleft}spider decompositions{\textquotedblright} was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of 2\&$\#$xa0;ln\&$\#$xa0;k, wherekis the number of terminals. However, the best known lower bound on the approximation ratio is (1-o(1))\&$\#$xa0;ln\&$\#$xa0;k, assuming thatNP⊈DTIME[nO(log\&$\#$xa0;log\&$\#$xa0;n)], by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of ln\&$\#$xa0;k. For the weighted case we develop a new decomposition theorem and generalize the notion of {\textquotedblleft}spiders{\textquotedblright} to {\textquotedblleft}branch-spiders{\textquotedblright} that are used to design a new algorithm with a worst case approximation factor of 1.5\&$\#$xa0;ln\&$\#$xa0;k. We then generalize the method to yield an approximation factor of (1.35+ε)\&$\#$xa0;ln\&$\#$xa0;k, for any constantε\>0. These algorithms, although polynomial, are not very practical due to their high running time, since we need to repeatedly find many minimum weight matchings in each iteration. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of 1.6103\&$\#$xa0;ln\&$\#$xa0;k. The techniques developed for this algorithm imply a method of approximating node weighted network design problems defined by 0{\textendash}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\&$\#$xa0;ln\&$\#$xa0;nby Guha and Khuller. 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+ε)\&$\#$xa0;ln\&$\#$xa0;nfor any fixedε\>0.},
isbn = {0890-5401},
doi = {10.1006/inco.1998.2754},
url = {http://www.sciencedirect.com/science/article/pii/S0890540198927547},
author = {Guha,Sudipto and Khuller, Samir}
}