Bibliographic Metadata
Bibliographic Metadata
- TitleLocal and online algorithms for facility location
- Author
- Examiner
- Published
- Institutional NotePaderborn, Univ., Diss., 2013
- AnnotationTag der Verteidigung: 28.10.2013
- LanguageEnglish
- Document TypesDissertation (PhD)
- URN
Links
- Social MediaShare
- Reference
- IIIF
Files
Classification
Zusammenfassung
Diese Arbeit beschäftigt sich mit dem Facility Location Problem. Dies ist ein Optimierungsproblem, bei dem festgelegt werden muss an welchen Positionen Ressourcen zur Verfügung gestellt werden, so dass diese von Nutzern gut erreicht werden können. Es sollen dabei Kosten minimiert werden, die zum einen durch Bereitstellung von Ressourcen und zum anderen durch Verbindungskosten zwischen Nutzern und Ressourcen entstehen. In dieser Arbeit werden drei Varianten des Problems modelliert und neue Algorithmen für sie entwickelt und bezüglich ihres Approximationsfaktors und ihrer Laufzeit analysiert. Jede dieser drei untersuchten Varianten hat einen besonderen Schwerpunkt. Bei der ersten Varianten handelt es sich um ein Online Problem, da hier die Eingabe nicht von Anfang an bekannt ist, sondern Schritt für Schritt enthüllt wird. Die Schwierigkeit hierbei besteht darin unwiderrufliche Entscheidungen treffen zu müssen ohne dabei die Zukunft zu kennen und trotzdem eine zu jeder Zeit gute Lösung angeben zu können. Der Schwerpunkt der zweiten Variante liegt auf Lokalität. Hier soll eine Lösung verteilt und nur mit Hilfe von lokalen Information berechnet werden. Schließlich beschäftigt sich die dritte Variante mit einer verteilten Berechnung, bei welcher nur eine stark beschränkte Datenmenge verschickt werden darf und dabei trotzdem ein sehr guter Approximationsfaktor erreicht werden muss. Die bei der Analyse der Approximationsfaktoren bzw. der Kompetitivität verwendeten TecTechniken basieren zum großen Teil auf Abschätzung der primalen Lösung mit Hilfe einer Lösung des zugehörigen dualen Problems. Für die Modellierung von Lokalität wird das weitverbreitete LOCAL Modell verwendet. In diesem Modell werden für die Algorithmen subpolynomielle obere Laufzeitschranken gezeigt.
Abstract
The topic of this thesis is approximation and online algorithms for an optimization problem known as Facility Location. This problem, or one of its many variants, arises as a sub problem in many practical applications, and is thus of significant importance in the field of Operations Research. Furthermore, it is also one of the most studied optimization problems in theoretical computer science with hundreds of research papers published during the last decades. In this thesis, we focus on the theoretical aspects of Facility Location by designing and analyzing approximation and online algorithms. Our algorithms deal with three distinct scenarios in which Facility Location occurs: (i) networks that are exposed to perpetual changes, (ii) wireless sensor networks with strong locality constraints, and (iii) distributed settings where the focus lies, first and foremost, on the quality of the computed approximation. Chapter 2 covers Scenario (i). It presents an online algorithm designed for a highly dynamic network where additional nodes are perpetually added. The difficulty here is that these new nodes' requests have to be handled efficiently without any knowledge of the network's future development. Scenario (ii) is considered in Chapter 3. Two distributed algorithms for wireless sensor networks are presented here. Due to the nodes' limited communication range, locality is of high importance in this scenario. Additional aspects like inaccurate measurement data, power consumption, and dynamics are also taken into account. Finally, Scenario (iii) is considered in Chapter 4. Our objective here is to distributedly compute a solution with an approximation ratio that is as close as possible to the best achievable ratio. In order to accomplish this, we allow, compared to Scenario (ii), a higher running time, but still require that the algorithm terminates in sub-linear time.
Stats
- The PDF-Document has been downloaded 58 times.
License/Rightsstatement
