Node Weighted Prize Collecting Steiner Tree

• INSTANCE: Graph $G=(V,E)$ , node weights $w\colon V\to \mathbb{R}^+$ , penalties $\pi\colon V\to \mathbb{R}^+$
• SOLUTION: A tree $T = (V_T, E_T)$ in $G$
• COST FUNCTION: $\sum_{v\in V_T}w(v)+\sum_{v\in V\setminus V_T}\pi (v)$
• OBJECTIVE: Minimize
• Approx.: Approximable within approximation ratio $O(\ln \vert V\vert)$ [77]
• Hardness: NP-hard to approximate within $c\cdot\ln \vert V\vert$ for some $c>0$ [77] For the online version of the problem, there exists an algorithm with polylogarithmic competitive ratio [59].