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 |