Minimum Broadcast Cover

• INSTANCE: A directed graph $G=(V,E)$ , a set $P$ consisting of all power levels at which a node can transmit, edge costs $c_{ij} : E(G) \rightarrow R_+$ , a source node $r \in V$ , an assignment operation $p^v _i : V(G) \rightarrow P$ and some constant $B \in R_+$ .

• SOLUTION: A node power assignment vector $A = [p^v _1, p^v _2 . . . p^v _{\vert V\vert}]$ inducing a directed graph $G' = (V, E')$ , where $E' = \{(i, j ) \in E: c_{ij} \leqslant p^v _i\}$ , in which there is a path from $r$ to any node of $V$ (all nodes are covered)

• COST FUNCTION: $\sum_{i \in V} p^v _i$

• OBJECTIVE: Minimize cost, at most $B$

• Approx.: There exists approximation algorithm that achieves the $O(\log N)$ approximation ratio [22].

• Hardness: NP-complete [22].

• Comment: There exists an approximation algorithm for the general version which achieves approximation ratio of $18 \log N$ .