A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from $frac{pi^2}{6}-frac{1}{36}+epsilonthickapprox 1.617$ to $frac{11}{7}thickapprox 1.571$. Moreover, we show that the algorithm of Khuller et al. for the strongly connected spanning subgraph problem, which achieves an approximation ratio of $1.61$, is $1.522$-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results via utilizing interesting properties for the existence of a second Hamiltonian cycle.
تحميل البحث