Universität zu Köln

Fuchs, Bernhard (2007). On the Approximability of Range Assignment Problems. PhD thesis, Universität zu Köln.

Preview

PDF diss-fuchs.pdf Download (1MB)

Abstract

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.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Über die Approximierbarkeit von Reichweitenzuordnungsproblemen German
Translated abstract:	Abstract Language Diese Arbeit behandelt Fragestellungen aus dem Bereich der kombinatorischen Optimierung, die sich bei der Datenübertragung in Funknetzen ergeben. Als Probleminstanz haben wir eine Menge von Sende- und Empfangsstationen mit ihren jeweiligen Entfernungen gegeben und sollen eine bestimmte Netzwerkeigenschaft herstellen, wobei die Gesamtenergieaufnahme des Netzwerks möglichst gering gehalten werden soll. Der Senderadius jeder einzelnen Station kann dabei individuell eingestellt werden. Die Lösung eines solchen Problems ist also eine Zuordnung von Senderadien zu den Stationen, die die geforderte Netzwerkeigenschaft mit dem niedrigst möglichem Gesamtenergiebedarf herstellt. Wir untersuchen in dieser Arbeit drei grundlegende Problemstellungen dieses Typs. Zunächst lassen wir auch sehr abstrakte Distanzfunktion zu, die nicht geometrischen Ursprungs sind. Wir analysieren die effiziente genaue und näherungsweise Lösbarkeit der einzelnen Probleme für verschiedene Arten von möglichen Distanzfunktionen. Unsere Untersuchungen zeigen auch wichtige Unterschiede der drei Problemstellungen auf, die nicht ohne weiteres augenscheinlich sind. Danach beschäftigen wir uns mit geometrischen Instanzen, die in der Forschung hinsichtlich Komplexität und Approximierbarkeit bereits etabliert sind. Unser Beitrag hierzu sind neue Reduktionen für die betrachteten Probleme, die sich als einfacher und flexibler als die bisher gebrauchten erweisen und somit neue und verbesserte Ergebnisse liefern. Offene Fragen aus früheren Arbeiten konnten mit unseren Reduktionen beantwortet werden. Wir behandeln auch Approximationsalgorithmen für diese Probleme. Wir untersuchen einen bereits bekannten Algorithmus hinsichtlich seiner Gütegarantie in Abhängigkeit von der Größe der Probleminstanz. Danach geben wir eine detaillierte Analyse zweier natürlicher "Greedy"-Algorithmen. Abschließend entwickeln wir einen neuen Approximationsalgorithmus für eines der drei Probleme, und geben ein Approximationsschema für spezielle geometrische Instanzen an. German
Creators:	Creators Email ORCID ORCID Put Code Fuchs, Bernhard bfuchs@zpr.uni-koeln.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-23311
Date:	2007
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language approximation algorithms, computational complexity, hardness of approximation, ad-hoc networks English
Date of oral exam:	25 October 2007
Referee:	Name Academic Title Schrader, Rainer Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/2331