Tech Report CS-92-54

A Nearly best-possible approximation algorithm for node-weighted Steiner trees

Philip Klein and R. Ravi

December 1992


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)