TY - CONF

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 - 1998

Y1 - 1998

N2 - We give the first non-trivial 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/3 log1/3 k), 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 non-trivial approximations to those as well. All these problems are known be as hard as set cover to approximate.

AB - We give the first non-trivial 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/3 log1/3 k), 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 non-trivial approximations to those as well. All these problems are known be as hard as set cover to approximate.

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

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

M3 - Paper

AN - SCOPUS:0032258737

SP - 192

EP - 200

T2 - Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms

Y2 - 25 January 1998 through 27 January 1998

ER -