Google Research

Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems

ICALP, Springer (2013)


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)

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work