TY - JOUR

T1 - The General Steiner Tree-Star problem

AU - Khuller, Samir

AU - Zhu, An

N1 - Funding Information:
* Corresponding author. This research was supported by an NSF CAREER Award CCR-9501355 and NSF Award CCR-9820965. E-mail addresses: samir@cs.umd.edu (S. Khuller), anzhu@cs.stanford.edu (A. Zhu). 1 This work was done while this author was at the University of Maryland. Currently supported by a GRPW fellowship from Bell Labs, Lucent Technologies.

PY - 2002/11/30

Y1 - 2002/11/30

N2 - The Steiner tree problem is defined as follows - given a graph G = (V,E) and a subset X ⊂ V of terminals, compute a minimum cost tree that includes all nodes in X. Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a "switch" cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set X cannot be connected to each other directly but only via the Steiner nodes V / X, is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of Θ(lnn) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of 5.16 and 5.

AB - The Steiner tree problem is defined as follows - given a graph G = (V,E) and a subset X ⊂ V of terminals, compute a minimum cost tree that includes all nodes in X. Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a "switch" cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set X cannot be connected to each other directly but only via the Steiner nodes V / X, is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of Θ(lnn) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of 5.16 and 5.

KW - Approximation algorithms

KW - Facility location

KW - Steiner trees

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

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

U2 - 10.1016/S0020-0190(02)00271-5

DO - 10.1016/S0020-0190(02)00271-5

M3 - Article

AN - SCOPUS:0037202492

VL - 84

SP - 215

EP - 220

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 4

ER -