Universität
Hamburg
Über Probleme bei der optimalen Standortbestimmung,
deren mögliche Lösungsmethoden und weitere Anwendungen
Freitag, 28. April 2006, 17
Uhr c.t., Hörsaal 6 des Geomatikums
Wie verteilt man eine
bestimmte Zahl von Postagenturen in einer Millionenstadt, so dass der weiteste
Weg eines Postkunden zu seiner nächstgelegenen Postagentur möglichst kurz ist?
Dieses bekannte „Post-Office Problem“ ist nur eine Variante des etwas
allgemeineren „k-center“-Problems,
welches man mathematisch wie folgt formuliert.
Zu einer gegebenen
natürlichen Zahl k und einer
endlichen Punktmenge X Ì Rn ist eine k-elementige Teilmenge Y Ì X gesucht, die ihren Überdeckungsradius r (Y,X) bez. X unter allen k-elementigen Teilmengen von X
minimiert. Der Überdeckungsradius r º r (Y,X) von Y bez. X wird dabei (zu einer gegebenen Metrik) gemessen durch die
minimale Distanz, mit der jeder Punkt aus X
höchstens um die Distanz r von seinem
nächstgelegenen Punkt in Y entfernt
ist.
Dieses diskrete
Optimierungsproblem ist im allgemeinen nicht effizient lösbar, was heuristische
Verfahren zur Bestimmung von suboptimalen Lösungen erfordert. Aufgrund seiner
Praxisrelevanz in zahlreichen industriellen Anwendungen ist das k-center-Problem ein beliebter
Forschungsgegenstand im „Operational Research“, wobei dort bisher überwiegend
graphentheoretische und kombinatorische Lösungsmethoden verwendet wurden.
In diesem Vortrag wird
zunächst die Komplexität des k-center-Problems
diskutiert, bevor eine „bestmögliche“ universelle Lösungsmethode vorgestellt
wird. Schließlich wird ein sehr effizienter geometrischer Algorithmus zur
approximativen Lösung des k-center-Problems
vorgeschlagen, der in vielen praxisrelevanten Anwendungen diese universelle
Lösungsmethode verbessert. Ausgewählte Anwendungsbeispiele aus der
Datenkompression belegen die gute Leistungsfähigkeit dieser neuen alternativen
Lösungsmethode.