Tech Report CS-92-54
A Nearly best-possible approximation algorithm for node-weighted Steiner trees
Philip Klein and R. Ravi
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.