- INSTANCE:
Wireless ad-hoc network
consisting of set of nodes
, location function
,
for each node
power levels
, a receiver sensitivity
propagation function
, set of destinations
,
a source
- SOLUTION:
An arborescence
rooted at
with
, power assignment
with
for all
such that for each directed edge
in
,
- COST FUNCTION:
- OBJECTIVE:
Minimize.
*Approx.:*Approximable within [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 time [86].

2015-04-27 Revision: 288 PDF version