- INSTANCE:
Graph
, cost function
, transmission range function
, some constant
.
- SOLUTION:
A connected graph
s.t.
and
,
.
- COST FUNCTION:
.
- OBJECTIVE:
Minimize.
*Approx.:*Approximable within for every [95] [5].*Hardness:*NP-hard for geometric instances in [37] and APX-complete for instances in [37].*Comment:*More practical approximation algorithm exist with approximation ratio [5] , [108].A variant called Min Power Symmetric Connectivity with Asymmetric Power Requirements is NP-hard to approximate within [5].

Min Power Symmetric Unicast is efficiently solvable in time [5]

2015-04-27 Revision: 288 PDF version