Improved Methods for Approximating Node Weighted Steiner Trees and
Connected Dominating Sets

Improved Methods for Approximating Node Weighted Steiner Trees and
Connected Dominating Sets

##### Files

##### Publication or External Link

##### Date

1998-10-15

##### Authors

Guha, Sudipto

Khuller, Samir

##### Advisor

##### Citation

##### DRUM DOI

##### Abstract

A greedy approximation algorithm based on ``spider decompositions''
was developed by Klein and Ravi for node weighted Steiner trees. 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 $\ln k$, assuming
that $NP \not\subseteq 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$.
This algorithm, although polynomial, is not very practical
due to its high running time; since we need to repeatedly find many
minimum weight matchings in each iteration.
We are able to generalize the method
to yield an approximation factor approaching $1.35 \ln k$.
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 the second algorithm imply a method of
approximating node weighted network design problems defined by 0-1 proper
functions.
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 a direct application of the methods developed in this paper we are
able to develop an algorithm with an approximation factor approaching
$1.35 \ln n$.
(Also cross-referenced as UMIACS-TR-97-80)