The minimum range assignment problem on linear radio networks

The minimum range assignment problem on linear radio networks

0.00 Avg rating0 Votes
Article ID: iaor2005373
Country: United States
Volume: 35
Issue: 2
Start Page Number: 95
End Page Number: 110
Publication Date: Feb 2003
Journal: Algorithmica
Authors: , , , ,
Abstract:

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. 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(hn3) 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(n3) time.

Reviews

Required fields are marked *. Your email address will not be published.