|
|
|
|
|
|
|
The MINIMUM RANGE ASSIGNMENT PROBLEM consists of assigning transmission ranges to the stations of a multi-hop packet radio network so as to minimize the total power consumption provided that the transmission range assigned to the stations ensures the strong connectivity of the network (i.e. each station can communicate with any other station by multi-hop transmission). The complexity of this optimization problem was studied by Kirousis, Kranakis, Krizanc, and Pelc (1997). In particular, they proved that, when the stations are located in a 3-dimensional Euclidean space, the problem is NP-hard and it admits a 2-approximation algorithm. On the other hand, they left the complexity of the 2-dimensional case as an open problem. As for the 3-dimensional case, we strengthen their negative result by showing that the problem is APX-complete, so, it does not admit a polynomial-time approximation scheme unless P=NP. We also solve the open problem discusses by Kirousis et al by proving that the 2-dimensional case remains NP-hard.
|
|
|
|
|
|
|
|