Approximation algorithms for directed Steiner problems

摘要: We obtain the first non-trivial approximation algorithms for Steiner Tree problem and Generalized in general directed graphs. Essentially no were known these problems. For Directed problem, we design a family of which achieve an ratio O(k^\epsilon) time O(kn^{1/\epsilon}) any fixed (\epsilon < 0), where k is number terminals to be connected. Problem, give algorithm achieves O(k^{2/3}\log^{1/3} k), pairs Related problems including Group tree Node Weighted several others can reduced preserving fashion solve, giving approximations those as well.