The minimum range assignment problem on linear radio networks

Given a set S of radio stations located on a line and an integer h greater than or equal to 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.