Minimum-Energy Broadcast Problem in Multi-hop Wireless Networks

• INSTANCE: A wireless ad hoc network $M = (N,L)$ , a source node s, and a terminal set $D = N - \{s\}$ .

• SOLUTION: Broadcast a message from any source node to all the other nodes.
• COST FUNCTION: Sum of transmission powers at all nodes.

• OBJECTIVE: Minimize.

• Approx.: For any source s, approximable within $2H(n -1)$ [94].

• Hardness: NP-hard [94].