An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree

Jochen Könemann, Sina Sadeghian, Laura Sanità

In the node-weighted prize-collecting Steiner tree problem (NW-PCST) we are given an undirected graph $G=(V,E)$, non-negative costs $c(v)$ and penalties $\pi (v)$ for each $v\in V$.…