Min Power Symmetric Connectivity

• INSTANCE: Graph $G=(V,E,c)$ , cost function $c: E \rightarrow R_+$ , transmission range function $r : V \rightarrow \mathbb{R}^+$ , some constant $k \geq 1$ .

• SOLUTION: A connected graph $T=(V,E_T,c)$ s.t. $r(e_1) \geq c(e)$ and $r(e_2) \geq c(e)$ , $e_1, e_2 \in V$ .

• COST FUNCTION: $\sum_{v \in V} r(v)^k$ .

• OBJECTIVE: Minimize.

• Approx.: Approximable within $5/3 + \epsilon$ for every $\epsilon >0$ [95] [5].

• Hardness: NP-hard for geometric instances in ${\mathbb{R}}^2$ [37] and APX-complete for instances in ${\mathbb{R}}^3$ [37].

• Comment: More practical approximation algorithm exist with approximation ratio $11/6$ [5] , [108].

  A variant called Min Power Symmetric Connectivity with Asymmetric Power Requirements is NP-hard to approximate within $(1- \epsilon) \ln \vert V\vert$ [5].

  Min Power Symmetric Unicast is efficiently solvable in time $O(\vert E\vert\log \vert V\vert)$ [5]