Blockseminar WS 98/99
Online-Algorithmen (044398)
Veranstalter: Hanno Lefmann
Online-Algorithmen werden bei unvollständiger Information über
eine Probleminstanz angewendet. So kann etwa eine Folge E1,
E2,..., En von mehreren Ereignissen auftreten und,
wenn man Ereignis Ei bearbeiten oder darauf reagieren muß,
kennt man nur die vorhergehenden Ereignisse E1,..., Ei-1,
aber nicht die folgenden Ei+1,..., En
und ihren eventuellen Einfluß. Typische Situationen sind etwa Jobangebote,
für oder gegen die man sich entscheiden muß, oder
Kauf-/Verkaufentscheidungen am Kapitalmarkt.
In diesem Seminar sollen für verschiedene Probleme Online-Algorithmen
vorgestellt und analysiert werden. Insbesondere möchte man die Qualität der
gelieferten Lösung mit der Qualität der optimalen Lösung
bei vollständiger Information vergleichen.
Die folgenden Themenbereiche sollen behandelt werden:
- Selbstorganisierende Datenstrukturen
- Das Server Problem
- Maschinenzuordnung
- Packungsprobleme
- Punktfärbungen von Graphen
- Datenmanagement
- Finanzprobleme.
Literaturgrundlage ist das Buch: `Online Algorithms -- The State of the Art'
von A. Fiat und G. J. Woeginger, Lecture Notes in Computer Science 1442,
Springer-Verlag, Berlin, 1998.
Teilnahmevoraussetzung sind Vordiplom und Vortragsübernahme.
Das Seminar soll als Blockseminar im März 1999 nach Absprache
mit den Teilnehmern durchgeführt werden.
Vorbesprechung und Themenvergabe:
Interessierte können sich bei mir melden (Tel. 755-4762).
Oder per email:
lefmann@ls2.cs.uni-dortmund.de