Approximation algorithms for directed Steiner problems

We give the first nontrivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed gra phs. These problems have several applications in network design and multica st routing. For both problems, the best ratios known before our work were t he trivial O(k)-approximations. For the directed Steiner tree problem, we d esign 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 fixed i > 1, where k is the number of terminals. Thus, an O(k(is an element of)) approximation ratio can be achi eved in polynomial time for any fixed is an element of > O. 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 t hat achieves an approximation ratio of O(k(2/3)log(1/3)k), where k is the n umber of pairs of vertices that are to be connected. Related problems inclu ding the group Steiner tree problem, the set TSP problem, and several other s in both directed and undirected graphs can be reduced in an approximation preserving fashion to the directed Steiner tree problem. Thus, we obtain t he first nontrivial approximations to those as well. All these problems are known to be as hard as the Set cover problem to approximate. (C) 1999 Acad emic Press.