Minimum-Energy Multicast Tree Problem

• INSTANCE: Wireless ad-hoc network $M = (N,L)$ consisting of set of nodes $N$ , location function $L : N \rightarrow \mathbb{Z}_{+}^2$ , for each node $v_i \in N, k$ power levels $w_{i,1} \leq w_{i,2} \leq ... \leq w_{i,k}$ , a receiver sensitivity $\vartheta >0$ propagation function $\gamma\colon \mathbb{Z}^2\times \mathbb{Z}^2\to \mathbb{R}_+$ , set of destinations $D\subseteq N$ , a source $s\in N\setminus D$

• SOLUTION: An arborescence $T=(V,E)$ rooted at $s$ with $D\subseteq V\subseteq N$ , power assignment $p=(p_i)_{v_i\in V}$ with $p_i\in \{w_{i,1},\ldots , w_{i,k}\}$ for all $v_i\in V$ such that for each directed edge $e=(v_i,v_j)$ in $T$ , $p_i-\gamma (L(v_i),L(v_j))\geq\vartheta$

• COST FUNCTION: $\sum_{v_i\:\mbox{non-leaf in $T$}}p_i$

• OBJECTIVE: Minimize.

• Approx.: Approximable within $O(((k + 1)n)^{1/\epsilon} \vert D\vert^{2/\epsilon}+kn^2$ [86].

• Hardness: NP-hard [86].

• Comment: When every node is equipped with the same type of battery, an approximation algorithm has a better performance ratio than that in the general case setting, and the algorithm takes $O(kn\vert D\vert \log \vert D\vert)$ time [86].