TY - JOUR

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

AU - Guha, Sudipto

AU - Khuller, Samir

N1 - Funding Information:
* Part of this work was done while at the University of Maryland and research was supported by NSF Research Initiation Award CCR-9307462. E-mail: sudipto cs.stanford.edu. -Research supported by NSF Research Initiation Award CCR-9307462 and NSF CAREER Award CCR-9501355. E-mail: samir cs.umd.edu.

PY - 1999/4/10

Y1 - 1999/4/10

N2 - 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 "spider decompositions" was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of 2 In k, where k is the number of terminals. However, the best known lower bound on the approximation ratio is (1 - o(1)) In k, assuming that NP ⊈ DTIME[no(log log n)], by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of In 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 In k. We then generalize the method to yield an approximation factor of (1.35+∈) In 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 In 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 In n by 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+∈) In n for any fixed ∈>0.

AB - 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 "spider decompositions" was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of 2 In k, where k is the number of terminals. However, the best known lower bound on the approximation ratio is (1 - o(1)) In k, assuming that NP ⊈ DTIME[no(log log n)], by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of In 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 In k. We then generalize the method to yield an approximation factor of (1.35+∈) In 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 In 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 In n by 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+∈) In n for any fixed ∈>0.

UR - http://www.scopus.com/inward/record.url?scp=0003115978&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0003115978&partnerID=8YFLogxK

U2 - 10.1006/inco.1998.2754

DO - 10.1006/inco.1998.2754

M3 - Article

AN - SCOPUS:0003115978

SN - 0890-5401

VL - 150

SP - 57

EP - 74

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -