The Minimum Range Assignment Problem on Linear Radio Networks

Given a set S of radio stations located on a line and an integer h ≥ 1 , the MIN ASSIGNMENT problem consists in finding a range assignment of minimum power consumption provided that any pair of stations can communicate in at most h hops. Previous positive results for this problem are only known when h=|S|‐1 or in the uniform chain case (i.e., when the stations are equally spaced). As for the first case, Kirousis et al. [7] provided a polynomial‐time algorithm while, for the second case, they derive a polynomial‐time approximation algorithm. This paper presents the first polynomial‐time, approximation algorithm for the MIN ASSIGNMENT problem. The algorithm guarantees a 2‐approximation ratio and runs in O(hn 3 ) time. We also prove that, for fixed h and for ‘well spaced’ instances (a broad generalization of the uniform chain case), the problem admits a polynomial‐time approximation scheme . This result significantly improves over the approximability result given by Kirousis {et al}. Both our approximation results are obtained via new algorithms that exactly solve two natural variants of the MIN ASSIGNMENT problem: the problem in which every station must reach a fixed one in at most h hops and the problem in which the goal is to select a subset of bases such that all the other stations must reach one base in at most h‐1 hops. Finally, we show that for h=2 the MIN ASSIGNMENT problem can be exactly solved in O(n 3 ) time.