132. Informatik-Kolloquium
Herr Matthias Englert
RWTH AachenLehrstuhl Algorithmen und Komplexität
"Das schnelle Multipolverfahren"
Mittwoch, 23.02.2008
09:15 - 10:45 Uhr, 1/346
Abstract:
Beim Online Minimum Makespan Scheduling geht es darum, Rechenjobs, die nacheinander ankommen, online so auf mehrere Rechner zu verteilen, dass die Gesamtzeit (Makespan), bis alle Jobs abgearbeitet sind, möglichst klein ist. In diesem Vortrag zeigen wir, wie man den Makespan durch eine eingeschränkte Umordnung der ankommenden Jobs deutlich verringern kann.Der Vortrag basiert auf einer gemeinsamen Arbeit mit Deniz Özmen und Matthias Westermann
Herr Heiko Röglin
RWTH AachenLehrstuhl Algorithmen und Komplexität
"Über die Bedeutung der kombinatorischen Struktur in Auslastungsspielen"
Mittwoch, 23.02.2008
11:30 - 13:00 Uhr, 1/346
Abstract:
Auslastungsspiele sind ein in der Ökonomik etabliertes Modell zur Allokation knapper Ressourcen. Ein solches Spiel besteht aus einer Menge von eigennützig handelnden Agenten, die um eine Menge von Ressourcen konkurrieren. Der Strategieraum eines Spielers ist dabei eine Menge von Teilmengen von Ressourcen, und jeder Spieler muss sich für eine Teilmenge von Ressourcen entscheiden, die er alloziert. Die Ressourcen können beispielsweise die Kanten eines Graphen sein, in dem jeder Spieler einen Pfad zwischen einer Quelle und einer Senke allozieren muss. Die Kosten, die den Spielern bei der Allokation einer Ressource entstehen, steigen mit der Anzahl der Spieler, die diese Ressource belegen, und jeder Spieler ist daran interessiert eine Teilmenge von Ressourcen mit möglichst wenig Kosten zu allozieren.In diesem Vortrag fassen wir aktuelle Ergebnisse über Auslastungsspiele zusammen. Insbesondere beschäftigen wir uns mit der Frage, welchen Einfluss die kombinatorische Struktur der Strategieräume auf die Komplexität der Berechnung von Nash-Gleichgewichten und die Konvergenzzeit der Best-Response-Dynamik hat. Wir diskutieren ebenfalls kurz erweiterte Modelle mit spielerspezifischen Kostenfunktionen und gewichteten Spielern.
Der Vortrag basiert auf gemeinsamen Arbeiten mit Heiner Ackermann und Berthold Vöcking.
