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:DagSemProc.06481.3,
  author =	{Carmi, Paz and Katz, Matthew},
  title =	{{Power Assignment in Radio Networks with Two Power Levels}},
  booktitle =	{Geometric Networks and Metric Space Embeddings},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6481},
  editor =	{Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1027},
  URN =		{urn:nbn:de:0030-drops-10277},
  doi =		{10.4230/DagSemProc.06481.3},
  annote =	{Keywords: Radio networks, power assignment, approximation algorithms, minimum spanning tree, disk graph}
}