24.03.2025, 12:30 Uhr
Universität Wien
Besprechungsraum 4.34
Währinger Str. 29
1090 Wien
Titel: Empirical evaluation of dynamic algorithms for the K-center problem
Kurzfassung:
Das k-Zentrum-Problem beschäftigt sich mit der Aufgabe, in einem Graphen k Zentren so zu bestimmen,
dass die maximale Entfernung eines Knotens zu seinem nächstgelegenen Zentrum minimiert wird. Diese
Aufgabe wird besonders herausfordernd, wenn der Graph dynamisch ist, also wenn Verbindungen
regelmäßig hinzugefügt oder entfernt werden. In solchen Fällen sind effiziente Algorithmen
erforderlich, um die Lösung kontinuierlich anzupassen.
Das Problem hat zahlreiche praktische Anwendungen, beispielsweise im Netzwerk- design, in der
Standortplanung und in Transportsystemen. In Transportsystemen, in denen sich Routen häufig ändern
oder gestört werden, ist eine schnelle Anpassung der Zentrumslokationen entscheidend, um einen
optimalen Betrieb zu gewährleisten.
Obwohl es umfangreiche Forschung zu statischen Algorithmen für das k-Zentrum- Problem gibt, die
starke theoretische Garantien bieten, sind diese Ansätze für dynamische Szenarien oft nicht
geeignet. Dynamische Algorithmen, wie sie in der wissenschaftlichen Literatur beschrieben werden,
bieten vielversprechende theoretische Vorteile, wurden jedoch bisher nur eingeschränkt in der
Praxis getestet. Dabei zeigt sich, dass die hohe algorithmische Komplexität solcher Verfahren in
realen Anwendungen oft zu Herausfor- derungen führt, insbesondere bei der effizienten Verarbeitung
von schnellen Änderungen. In dieser Arbeit wird gezeigt, dass dynamische Algorithmen, wenn sie
gezielt opti- miert und angepasst werden, statischen Ansätzen in dynamischen Szenarien überlegen
sein können. Durch systematische Experimente mit verschiedenen Kombinationen von Algorithmen
konnten signifikante Leistungssteigerungen erzielt werden. Die Ergebnisse zeigen, dass dynamische
k-Zentrum-Algorithmen nicht nur theoretisch, sondern auch
praktisch eine effektive Lösung für reale dynamische Probleme darstellen.