04-10-0513-vu Online Optimization

Veranstaltungsdetails

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.

Kleingruppe(n)
Die Veranstaltung ist in die folgenden Kleingruppen aufgeteilt:
  • 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."

    Prof. Dr. Yann Disser

Literatur
Termine
Datum Von Bis Raum Lehrende
1 Mi, 19. Okt. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
2 Mi, 26. Okt. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
3 Mi, 2. Nov. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
4 Mi, 9. Nov. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
5 Mi, 16. Nov. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
6 Mi, 23. Nov. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
7 Mi, 30. Nov. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
8 Mi, 7. Dez. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
9 Mi, 14. Dez. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
10 Mi, 21. Dez. 2016 11:40 13:20 S306/052 Prof. Dr. Yann Disser
11 Mi, 11. Jan. 2017 11:40 13:20 S306/052 Prof. Dr. Yann Disser
12 Mi, 18. Jan. 2017 11:40 13:20 S306/052 Prof. Dr. Yann Disser
13 Mi, 25. Jan. 2017 11:40 13:20 S306/052 Prof. Dr. Yann Disser
14 Mi, 1. Feb. 2017 11:40 13:20 S306/052 Prof. Dr. Yann Disser
15 Mi, 8. Feb. 2017 11:40 13:20 S306/052 Prof. Dr. Yann Disser
Übersicht der Kurstermine
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
Lehrende
Prof. Dr. Yann Disser