Navigation

Springe zum Hauptinhalt
Fakultät für Informatik
Informatik-Kolloquien

132. Informatik-Kolloquium

Herr Matthias Englert

RWTH Aachen
Lehrstuhl 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 Aachen
Lehrstuhl 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.

Alle interessierten Personen sind herzlich eingeladen!

Presseartikel