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