Range Augmentation Problems in Static Ad-Hoc Wireless Networks

Given a set V of n stations, a transmission power cost function c : V×V↣R+∪{+∞} , an initial power assignment p0:V↣R+ , and a connectivity property π, a range augmentation problem consists of finding a minimum power augmentation assignment p such that p f (·) = p 0(·) + p(·) satisfies property π. In this paper, we focus on the problem of biconnecting an already existing connected network, to make it resilient to the failure of either a wireless link or a station.For these problems we give a H2n -approximation greedy algorithm (where Hn is the n-th harmonic number) after proving that they are both not approximable within (1 – o(1)) ln n, unless NP⊂DTIME(nO(loglogn)) , even when c is a distance cost function restricted to three power levels, or it is a distance cost function and p 0 induces a tree network. Moreover, we prove that both problems remain APX-hard even if the initial power assignment is uniform. In this latter scenario, we finally show that any λ-approximation algorithm for the corresponding problem in wired networks, is a 2λ-approximation algorithm for the wireless case.