TY - JOUR

T1 - Approximation Algorithms for Directed Steiner Problems

AU - Charikar, Moses

AU - Chekuri, Chandra

AU - Cheung, To Yat

AU - Dai, Zuo

AU - Goel, Ashish

AU - Guha, Sudipto

AU - Li, Ming

N1 - Funding Information:
* This paper reports the combined version of the two papers w6, 7x, the results of which were obtained independently by the respective authors. A preliminary version appeared in the ``Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998 w5x. ²Corresponding author. Supported by an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. E-mail: [email protected]. ³ Supported by an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. E-mail: [email protected]. §E-mail: [email protected]. ¶Supported by City University of Hong Kong. E-mail: [email protected]. 5Supported by ARO Grant DAAH04-95-1-0121 and NSF Grant CCR9304971. E-mail: [email protected]. ** Supported by an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. E-mail: [email protected]. ²²Supported in part by the NSERC Operating Grant OGP0046506, ITRC, and a CGAT grant. The work was done when the author was visiting City University of Hong Kong. E-mail: [email protected],ca.

PY - 1999/10

Y1 - 1999/10

N2 - We give the first nontrivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing. For both problems, the best ratios known before our work were the trivial O(k)-approximations. For the directed Steiner tree problem, we design a family of algorithms that achieves an approximation ratio of i(i - 1)k1/i in time O(nik2i) for any fixed i > 1, where k is the number of terminals. Thus, an O(k∈) approximation ratio can be achieved in polynomial time for any fixed ∈ > 0. Setting i = log k, we obtain an O(log2 k) approximation ratio in quasi-polynomial time. For the directed generalized Steiner network problem we give an algorithm that achieves an approximation ratio of O(k2/3log1/3k), where k is the number of pairs of vertices that are to be connected. Related problems including the group Steiner tree problem, the set TSP problem, and several others in both directed and undirected graphs can be reduced in an approximation preserving fashion to the directed Steiner tree problem. Thus, we obtain the first nontrivial approximations to those as well. All these problems are known to be as hard as the Set cover problem to approximate.

AB - We give the first nontrivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing. For both problems, the best ratios known before our work were the trivial O(k)-approximations. For the directed Steiner tree problem, we design a family of algorithms that achieves an approximation ratio of i(i - 1)k1/i in time O(nik2i) for any fixed i > 1, where k is the number of terminals. Thus, an O(k∈) approximation ratio can be achieved in polynomial time for any fixed ∈ > 0. Setting i = log k, we obtain an O(log2 k) approximation ratio in quasi-polynomial time. For the directed generalized Steiner network problem we give an algorithm that achieves an approximation ratio of O(k2/3log1/3k), where k is the number of pairs of vertices that are to be connected. Related problems including the group Steiner tree problem, the set TSP problem, and several others in both directed and undirected graphs can be reduced in an approximation preserving fashion to the directed Steiner tree problem. Thus, we obtain the first nontrivial approximations to those as well. All these problems are known to be as hard as the Set cover problem to approximate.

KW - Approximation algorithm

KW - Directed graph

KW - Steiner tree problem

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

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

U2 - 10.1006/jagm.1999.1042

DO - 10.1006/jagm.1999.1042

M3 - Article

AN - SCOPUS:0001490886

SN - 0196-6774

VL - 33

SP - 73

EP - 91

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -