A NEARLY BEST-POSSIBLE APPROXIMATION ALGORITHM FOR NODE-WEIGHTED STEINER TREES

We give the first approximation algorithm for the node-weighted Steine r tree problem. Its performance guarantee is within a constant factor of the best possible unless ($) over bar P superset of or equal to NP. (($) over bar P stands for the complexity class deterministic quasi-p olynomial time, or DTIME[n(polylog) (n)].) Our algorithm generalizes t o handle other network-design problems. (C) 1995 Academic Press, Inc.