BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-97-56
       ENTRY:: March 24, 1997
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Approximation Algorithms for Directed Steiner Tree Problems
        TYPE:: Technical Note
      AUTHOR:: Charikar, Moses
      AUTHOR:: Chekuri, Chandra
      AUTHOR:: Goel, Ashish
      AUTHOR:: Guha, Sudipto
        DATE:: March 1997
       PAGES:: 13
    ABSTRACT:: We obtain the first non-trivial approximation algorithms for
               the Steiner Tree problem and the Generalized Steiner Tree
               problem in general directed graphs. Essentially no
               approximation algorithms were known for these problems. For
               the Directed Steiner Tree problem, we design a family of
               algorithms which achieve an approximation ratio of
               O(k^\epsilon) in time O(kn^{1/\epsilon}) for any fixed
               (\epsilon > 0), where k is the number of terminals to be
               connected. For the Directed Generalized Steiner Tree Problem,
               we give an algorithm which achieves an approximation ratio of
               O(k^{2/3}\log^{1/3} k), where k is the number of pairs to be
               connected. Related problems including the Group Steiner tree
               problem, the Node Weighted Steiner tree problem and several
               others can be reduced in an approximation preserving fashion
               to the problems we solve, giving the first non-trivial
               approximations to those as well.
       NOTES:: [Adminitrivia V1/Prg/19970324]
         END:: STAN//CS-TN-97-56