Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
Abstract
Moss and Rabani [12] study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an O(logn)-approximation algorithm for the prize-collecting node-weighted Steiner tree problem (PCST)
Research Areas
