On the Approximability of Range Assignment Problems

Fuchs, Bernhard (2007) On the Approximability of Range Assignment Problems. PhD thesis.


We consider combinatorial optimization problems motivated by the following scenario. We are given a set of radio stations which can all send and receive data via wireless communication. Each radio station can be assigned an individual range up to which it transmits data. Given a certain connectivity requirement, the optimization task is to find a configuration of ranges (or range assignment) of minimal total power consumption providing the required network property. A problem of this kind is called range assignment problem. Three important problems of this type are examined in this thesis. First, we choose a quite abstract approach, allowing arbitrary distance functions without geometrical interpretation. We give the first thorough structural analysis of these problems in different setups. Our results identify easy cases as well as hard ones in terms of complexity as well as various levels of approximability for the individual problems. They also reveal interesting differences between the three problems themselves. We then turn to geometrical instances, on which there already exists a line of research regarding complexity and approximability in the literature. We contribute to this research by designing new reductions which are more simple and versatile than the ones used before, and produce new and better results. Using our reductions we can solve open problems posed in prior work. In the last chapter, we turn to approximation algorithms. We give a tight analysis of a well-known approximation algorithm for two of the problems as a function of the input size. A thorough analysis of two natural greedy paradigms is given, with tight results in the general and many special cases. We conclude with the design and analysis of a new approximation algorithm for one problem, and identify the first approximation scheme for some special geometric instances.

Download: [img] Postscript - Accepted Version
Download (1MB) | Preview
Download: [img] PDF - Accepted Version
Download (841kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2008-576
Depositing User: Bernhard Fuchs
Date Deposited: 23 Jul 2008 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/576