×

Power assignment in radio networks with two power levels. (English) Zbl 1108.90015

Summary: We study the power-assignment problem in radio networks, where each radio station can transmit in one of two possible power levels, corresponding to two ranges – short and long. We show that this problem is NP-hard, and we present an \(O(n^{2})\)-time assignment algorithm such that the number of transmitters that are assigned long range by the algorithm is at most \((11/6)\) times the number of transmitters that are assigned long range by an optimal algorithm. We also present a \((9/5)\)-approximation algorithm for this problem whose running time is considerably higher.

MSC:

90B18 Communication networks in operations research
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
68W25 Approximation algorithms