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 NP-hard, 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 Minimum-Area 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 n-1 disks whose diameters are the edges in T. We prove that the Euclidean minimum spanning tree of P is a constant-factor approximation for MAST. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (MARA) problem, for the Minimum-Area Connected Disk Graph (MACDG) problem, and for the Minimum-Area 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.

@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 =	{1862-4405},
  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}
}