Report Number: CS-TN-97-56
Institution: Stanford University, Department of Computer Science
Title: Approximation Algorithms for Directed Steiner Tree Problems
Author: Charikar, Moses
Author: Chekuri, Chandra
Author: Goel, Ashish
Author: Guha, Sudipto
Date: March 1997
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.
http://i.stanford.edu/pub/cstr/reports/cs/tn/97/56/CS-TN-97-56.pdf