Approximation algorithms for directed Steiner problems

Moses Charikar, Chandra Chekuri, To yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li

Research output: Contribution to conferencePaperpeer-review


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.

Original languageEnglish (US)
Number of pages9
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 25 1998Jan 27 1998


OtherProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Approximation algorithms for directed Steiner problems'. Together they form a unique fingerprint.

Cite this