Steiner Activation Network

• INSTANCE: Graph $G=(V,E)$ , monotone activation function $f_e\colon \mathbb{R}^+\times\mathbb{R}^+\to\{0,1\}$ for each edge $e\in E$ , terminal sets $R_1,\ldots , R_k\subseteq V$
• SOLUTION: Assignment $x=(x_v)_{v\in V}\in \mathbb{R}^{\vert V\vert}$ such that the subgraph induced by the activated edges $e=\{u,v\}$ (i.e. $f_e(x_u,x_v)=1$ ) connects every terminal set $R_i$
• COST FUNCTION: $\sum_{v\in V}x_v$
• OBJECTIVE: Minimize
• Approx.: Approximable within approximation ratio $O(\log k)$ [93]
• Hardness: NP-hard to approximate within $o(\log k)$ [93]