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.

Authors and Affiliations

1. Dipartimento di Matematica, Università di Roma ``Tor Vergata'', Via della Ricerca Scientifica, 00133 Rome, Italy. clementi@mat.uniroma2.it, pennA@mat.uniroma2.it., Italy

   E. F. Clementi &  Penna

2. MASCOTTE Project, I3S/INRIA Sophia Antipolis, CNRS/INRIA/Université de Nice-Sophia Antipolis, 2004 route des lucioles, B.P.93, F 06902 Sophia Antipolis, France. ferreira@sophia.inria.fr, perennes@sophia.inria.fr., France

   Ferreira &  Perennes

3. Dipartimento di Scienze dell'informazione, Università di Roma ``La Sapienza'', Via Salaria 113, I00198 Roma, Italy. silver@dsi.uniroma1.it., Italy

   Silvestri

Reprints and permissions