Tech Report CS-92-54
A Nearly best-possible approximation algorithm for node-weighted Steiner trees
Philip Klein and R. Ravi
December 1992
Abstract:
We give the first approximation algorithm for the node-weighted Steiner tree problem. Its performance guarantee is within a constant factor of the best possible unless $\tilde P \supseteq NP$. Our algorithm generalizes to handle other network design problems.
(complete text in pdf or gzipped postscript)