TY - GEN
T1 - Improved methods for approximating node weighted steiner trees and connected dominating sets (Extended Abstract)
AU - Guha, Sudipto
AU - Khuller, Samir
PY - 1998
Y1 - 1998
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 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 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 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 lnk. We then generalize the method to yield an approximation factor of (1.35+ε) lnk, 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 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 lnn due to 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 + ε) lnn 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 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 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 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 lnk. We then generalize the method to yield an approximation factor of (1.35+ε) lnk, 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 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 lnn due to 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 + ε) lnn for any fixed ε > 0.
UR - http://www.scopus.com/inward/record.url?scp=84887069789&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84887069789&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-49382-2_6
DO - 10.1007/978-3-540-49382-2_6
M3 - Conference contribution
AN - SCOPUS:84887069789
SN - 3540653848
SN - 9783540653844
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 54
EP - 66
BT - Foundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings
T2 - 18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998
Y2 - 17 December 1998 through 19 December 1998
ER -