1.61-approximation for min-power strong connectivity with two power levels

Given a directed simple graph $$G=(V,E)$$ G = ( V , E ) and a cost function $$c:E \rightarrow R_+$$ c : E → R + , the power of a vertex $$u$$ u in a directed spanning subgraph $$H$$ H is given by $$p_H(u) = \max _{uv \in E(H)} c(uv)$$ p H ( u ) = max u v ∈ E ( H ) c ( u v ) , and corresponds to the energy consumption required for wireless node $$u$$ u to transmit to all nodes $$v$$ v with $$uv \in E(H)$$ u v ∈ E ( H ) . The power of $$H$$ H is given by $$p(H) = \sum _{u \in V} p_H(u)$$ p ( H ) = ∑ u ∈ V p H ( u ) . Power Assignment seeks to minimize $$p(H)$$ p ( H ) while $$H$$ H satisfies some connectivity constraint. In this paper, we assume $$E$$ E is bidirected (for every directed edge $$e \in E$$ e ∈ E , the opposite edge exists and has the same cost), while $$H$$ H is required to be strongly connected. Moreover, we assume $$c:E \rightarrow \{A,B\}$$ c : E → { A , B } , where $$0 \le A