Lehrende: Prof. Dr. Yann Disser
Veranstaltungsart: Vorlesung und Übung
Orga-Einheit: FB04 Mathematik
Anzeige im Stundenplan: Online-Opt.
Fach:
Anrechenbar für:
Semesterwochenstunden: 3
Unterrichtssprache: Deutsch
Min. | Max. Teilnehmerzahl: - | -
Lehrinhalte: Einführung in die Online Optimierung, List Access, Paging, randomisierte online Algorithmen, Yao's Prinzip, Load Balancing und online Scheduling, k-Server Probleme, ...
Literatur: - Borodin, El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 2005. - Amos Fiat, Gerhard J. Woeginger. Online Algorithms: The State of the Art. Springer, 1998. (Weitere Literatur wird im Kursverlauf angegeben.)
Voraussetzungen: Grundlagen der Optimierung / der Algorithmik
Offizielle Kursbeschreibung: Online Optimierung beschäftigt sich mit Optimierungsproblemen, bei denen Teile der Eingabedaten zu Beginn noch unbekannt sind. Die fehlenden Daten werden werden erst über die Zeit verfügbar, während der online Optimierungsalgorithmus auf Basis der bekannten Informationen bereits unwiderrufliche Entscheidungen trifft. Ein typisches Beispiel hierfür ist die Aufzugssteuerung: Hier wollen wir die Wartezeit der Benutzer minimieren, müssen aber sofort ("on-line") entscheiden, wie wir auf Anfragen reagieren, ohne zu wissen, welche Anfragen in Zukunft beantwortet werden müssen. Gibt es gute Algorithmen für solche Probleme? In diesem Kurs werden wir eine Übersicht über grundlegende Techniken zum Entwurf und zur Analyse von online Algorithmen für kombinatorische Optimierungsprobleme geben. Wir werden sowohl klassische sowie aktuelle Forschungsresultate behandeln. Der Kurs wird entweder auf Deutsch oder auf Englisch gehalten, je nach Zuhörerwunsch.
Online Optimization Übung
Prof. Dr. Yann Disser
Do, 3. Nov. 2016 [15:20]-Do, 9. Feb. 2017 [17:00]
Online Optimization Übung "Ich nehme nicht am Übungsbetrieb teil."