A Polynomial Time Subpolynom-Approximation Scheme for the Acyclic Directed Steiner Tree Problem
Alex Zelikovsky · 1994
The acyclic directed Steiner tree problem (ADSP) requires a minimal outward tree within an acyclic digraph with edge costs G = (V; E; d) which connects a root r with a distinguished subset S ae V , #S = k. The best possible performance guarantee of any polynomial approximation algorithm for ADSP cannot be less than 1 4 log k unless ~ P ' NP . The presented series of heuristics A n has a performance guarantee k 1 n (1 + ln k) n\\Gamma1 . This implies that that fA n g is a polynomial exp[ p 4 ln k ln(ln k + 1) \\Gamma ln(ln k+1)]-approximation scheme for ADSP. Keywords: Algorithms, approximations, Steiner tree Research partially supprted by the Volkswagen--Stiftung. 1 Introduction The general Steiner tree problem in graphs requires a minimum cost tree spanning a distinguished node set S in a network G. This problem is investigated for different types of networks. We will mention below the following cases: usual networks with edge costs (NSP), node-weighted networks (NWSP) wh...