Prize-Collecting Node Weighted Survivable Network Design

• INSTANCE: Graph $G=(V,E)$ , connectivity requirements $r(u,v)\in \mathbb{Z}_{\geq 0}$ and penalties $\pi (u,v) \geq 0$ for all $u,v\in V$ , node weights $w\colon V\to \mathbb{R}_+$
• SOLUTION: Subgraph $H$ in $G$
• COST FUNCTION: weight $w(H)$ of $H$ plus the sum of penalties $\pi (u,v)$ for which $H$ does not contain at least $r(u,v)$ edge-disjoint $u-v$ paths
• OBJECTIVE: Minimize
• Approx.: Approximable within approximation ratio $O(k^2\log n)$ , where $k=\max_{u,v\in V}r(u,v)$ [31]. Approximable within approximation ratio $O(k)$ for minor-closed families of graphs [30].