# Tech Report CS-92-54

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

### 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)