Abstract
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 NPhard, and 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 an (9/5)approximation algorithm for this problem whose running time is considerably higher.
Next, we formulate and study the MinimumArea Spanning Tree (MAST)problem: Given a set P of n points in the plane, find a spanning tree of P of minimum "area," where the area of a spanning tree T is the area of the union of the n1 disks whose diameters are the edges in T. We prove that the Euclidean minimum spanning tree of P is a constantfactor approximation for MAST. We then apply this result to obtain constantfactor approximations for the MinimumArea Range Assignment (MARA) problem, for the MinimumArea Connected Disk Graph (MACDG) problem, and for the MinimumArea Tour (MAT) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.
BibTeX  Entry
@InProceedings{carmi_et_al:DSP:2007:1027,
author = {Paz Carmi and Matthew Katz},
title = {Power Assignment in Radio Networks with Two Power Levels},
booktitle = {Geometric Networks and Metric Space Embeddings},
year = {2007},
editor = {Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff},
number = {06481},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1027},
annote = {Keywords: Radio networks, power assignment, approximation algorithms, minimum spanning tree, disk graph}
}
Keywords: 

Radio networks, power assignment, approximation algorithms, minimum spanning tree, disk graph 
Collection: 

06481  Geometric Networks and Metric Space Embeddings 
Issue Date: 

2007 
Date of publication: 

01.06.2007 