View article

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 P̃ ⊇ NP. (P̃ stands for the complexity class deterministic quasi-polynomial time, or DTIME[n^{polylog n}].) Our algorithm generalizes to handle other network-design problems.