Sommersemester 2001
Thema: Facility-Location-Probleme
In diesem Hauptseminar behandeln wir anhand neuer Originalarbeiten das Facility-Location Problem, mit und ohne Kapazitäten. Für dieses NP-schwere diskrete Optimierungsproblem, dessen praktische Anwendbarkeit auf der Hand liegt, waren bis vor wenigen Jahren keine Approximationsalgorithmen bekannt, dies hat sich nun aber mit einer ganzen Reihe interessanter Arbeiten geändert: nun gibt es gleich mehrere mit unterschiedlichen, auch auf andere Probleme anwendbaren Techniken (LP-Rundung, Primal-Duale Methode, Lokale Suche), die wir im Seminar kennenlernen werden.
montags 14-16 im Seminarraum des Instituts
| Nr. | Datum | Name | Thema | Betreuung |
|---|---|---|---|---|
| 1 | 23.04. | Ute Zimmermann |
Hochbaum, Shmoys: A best possible heuristic for the k-center problem Hsu, Nemhauser: Easy and hard bottleneck location problems |
Jürgen Werber |
| 2 | 30.04. | Anna Pauli | Cornuejols, Fisher, Nemhauser: On the uncapacitated location problem | Matthias Müller-Hannemann |
| 3 | 7.05. | Normann Pankratz | Shmoys, Tardos, Aardal: Approximation algorithms for facility location problems | Matthias Müller-Hannemann |
| 4 | 14.05. | Christina Steiner | Guha, Khuller: Greedy strikes back: Improved facility location algorithms | Jürgen Werber |
| 5 | 21.05. | Patrick Lechner | Chudak: Improved approximation algorithms for uncapacitated facility location | Ulrich Brenner |
| 6 | 28.05. | Alexander Sonnikow | Chudak, Shmoys: Improved approximation algorithms for a capacitated facility location problem | Sven Peyer |
| 7 | 11.06. | Zoltan Istvan Aba | Korupolu, Plaxton, Rajaraman: Analysis of a local search heuristic for facility location problems | Ulrich Brenner |
| 8 | 18.06. | Christian Panten | Chudak, Williamson: Improved approximation algorithms for capacitated facility location problems | Sven Peyer |
| 9 | 25.06. | Martin Maier | Jain, Vazirani: Approximation algorithms for metric facility location and k-median problems using the primal-dial schema and Lagrangian relaxation | Karsten Weihe |
| 10 | 2.07. | Christian Plog | Charikar, Guha: Improved combinatorial algorithms for the facility location and k-median problems | Karsten Weihe |
| 11 | 9.07. | Meike Jungebloed | Guha, Khuller: Connected facility location problems | Karsten Weihe |
Voraussetzungen:
Vordiplom und mindestens eine (besser mehrere) Vorlesung aus dem Bereich der Diskreten Mathematik oder Mathematischen OptimierungScheinkriterien:
erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive MitarbeitProf. Dr. B. Korte, Dr. Matthias Müller-Hannemann, Dr. J. Vygen, Prof. Dr. K. Weihe