Forschungsinstitut für Diskrete Mathematik

Seminar Diskrete Optimierung

Wintersemester 2006/07

Thema: Optimierung in Netzwerken

Termin: montags 10-12 Uhr
Unter dem Oberbegriff "multicommodity flows" fasst man Optimierungsprobleme in Netzwerken zusammen, bei denen verschiedene Nutzer eine bestimmte Nachfrage haben, die in einem gegebenen Netzwerk mit knappen Ressourcen realisiert werden soll. Im einfachsten Fall ist für jeden Nutzer ein Weg zwischen vorgegebenen Endpunkten gesucht. Die Kanten des Netzwerkes haben oft Kapazitätsbeschränkungen. Außerdem ist die Leistungsfähigkeit einer Kante (die sich zum Beispiel in der zu ihrer Durchquerung benötigten Zeit widerspiegeln kann) oft von ihrer Auslastung abhängig. Anwendungen dieser Probleme sind etwa Internet-Routing, Verkehrssteuerung, Mautsysteme, sowie Routing im Chip-Design. In jüngster Zeit sind für verschiedene Multicommodity-Flow-Probleme erheblich effizientere Algorithmen gefunden worden, die auch für Probleme in sehr großen Netzwerken mit sehr vielen Nutzern schnell gute Lösungen finden. Außerdem wurden Verbindungen zur Spieltheorie untersucht. Zum Beispiel fragt man sich, wie viel schlechter als das globale Optimum eine Lösung ist, die man erhält, wenn jeder Nutzer stets aufs Neue für sich optimiert (wie es etwa im Berufsverkehr annähernd der Fall ist); dieses Verhältnis heißt auch "price of anarchy". Als Einführung in Grundlagen können die Abschnitte 19.1 und 19.2 des Buches "Combinatorial Optimization" (Korte und Vygen, Springer, 3. Auflage 2006) dienen.
Nr. Datum Name Thema Betreuung
1 16.10. Sandra Kosmalla G. Karakostas: Faster approximation schemes for fractional multicommodity flow problems Jürgen Werber
2 23.10. Michael Gester J. Vygen: Near-optimum global routing with coupling, delay bounds, and power consumption Dirk Müller
3 30.10. Richard Schmied D. Bienstock, G. Iyengar: Approximating fractional packings and covering in O*(1/ε) iterations Stephan Held
4 6.11. Hanna Sdunzik T. Roughgarden, E. Tardos: How bad is selfish routing? Sven Peyer
5 13.11. Marcel Dhiflaoui L. Fleischer: Linear tolls suffice: new bounds and algorithms for tolls in single source networks Jens Maßberg
6 22.1.2006 Markus Moll E. Koutsoupias, C. Papadimitriou: Worst-case equilibria Christoph Bartoschek

Voraussetzungen:

Vordiplom und mindestens eine Vorlesung (besser mehrere) aus dem Bereich der Diskreten Mathematik oder Mathematischen Optimierung.

Scheinkriterien:

Erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive Mitarbeit
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Dr. U. Brenner