Approximation algorithms for directed Steiner problems

We give the rst 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)k 1=i in time O(n i k 2i ) for any xed i > 1, where k is the number of terminals. Thus, an O(k ) approximation ratio can be achieved in polynomial time for any xed > 0. Setting i = log k, we obtain an O(log 2 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(k 2=3 log 1=3 k), where k is the number of pairs of vertices that are to be connected. Related problems including the group Steiner tree problem,...