A series of approximation algorithms for the acyclic directed steiner tree problem

Given an acyclic directed network, a subsetS of nodes (terminals), and a rootr, theacyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths fromr to each terminal. It is known that unlessNP⊆DTIME[n ^polylogn ] no polynomial-time algorithm can guarantee better than (lnk)/4-approximation, wherek is the number of terminals. In this paper we give anO(k ^ε)-approximation algorithm for any ε>0. This result improves the previously knownk-approximation. This research was supported in part by Volkswagen-Stiftung and Packard Foundation.