Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1994 Copyright 1994 Universität Bonn, Institut für Informatik, Abt. V 85113 A Polynomial Time Subpolynom-Approximation Scheme for the Acyclic Directed Steiner Tree Problem Alexander Zelikovsky [Download PostScript] [Download PDF] 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\subset V$, $\# S = k$. The best possible performance guarantee of any polynomial approximation algorithm for ADSP cannot be less than ${1\over 4} \log k$ unless $\tilde{P} \supseteq NP$. The presented series of heuristics $A_n$ has a performance guarantee $k^{1\over n}(1+\ln k)^{n-1}$. This implies that that $\{ A_n \}$ is a polynomial $\exp[\sqrt{4\ln k \ln(\ln k+1)}- \ln (\ln k +1)]$-approximation scheme for ADSP. Last Change: 11/05/14 at 09:53:23  English Universität Bonn -> Institut für Informatik -> Abteilung V