2014/02/24 by Karim Abu-Affash, Abu-Affash, Karim, Paz Carmi +3
Computer Science · Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.1402.5783
arxiv created 2014/02/24 · arxiv updated 2014/02/25
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 (π2)/(6)-(1)/(36)+ε\thickapprox 1.617 to (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.