Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems

摘要: We consider a class of optimization problems where the input is an undirected graph with two weight functions defined for each node, namely node's profit and its cost. The goal to find connected set nodes low cost high profit. present approximation algorithms three natural criteria that arise in this context, all which are NP-hard. budget problem asks maximizing subject constraint on quota requires minimizing Finally, prize collecting calls plus (here interpreted as penalty) complement set. For problems, our give guarantee $O(\log n)$, $n$ number nodes. To best knowledge, these first results problem, both at least hard approximate cover. improve previous $O(\log^2 n)$ result Guha et al. Our methods involve new theorems relating tree packings (node) cut conditions. also show similar (with better bounds) using edge These imply bounds analogous costs comparable known (constant factor) bounds.