Forschungsinstitut für Diskrete Mathematik

Seminar Diskrete Optimierung

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 Optimierung

Scheinkriterien:

erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive Mitarbeit
Prof. Dr. B. Korte, Dr. Matthias Müller-Hannemann, Dr. J. Vygen, Prof. Dr. K. Weihe