# Hardness Results for the Power Range Assignment Problem in Packet Radio Networks

##
Paolo Penna

### Univ. of Rome "Tor Vergata", Math. Dept.

### Résumé:

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.