Universität zu Köln

On the Approximability of Range Assignment Problems

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

[img]
Preview
PDF
Download (1751Kb) | Preview

    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 abstract:
    AbstractLanguage
    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:
    CreatorsEmail
    Fuchs, Bernhardbfuchs@zpr.uni-koeln.de
    URN: urn:nbn:de:hbz:38-23311
    Subjects: Data processing Computer science
    Uncontrolled Keywords:
    KeywordsLanguage
    approximation algorithms, computational complexity, hardness of approximation, ad-hoc networksEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: English
    Date: 2007
    Date Type: Completion
    Date of oral exam: 25 October 2007
    Full Text Status: Public
    Date Deposited: 11 Jun 2008 12:12:59
    Referee
    NameAcademic Title
    Schrader, RainerProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/2331

    Actions (login required)

    View Item