Seminar (Hauptstudium)
Seminar Diskrete Optimierung
Prof. Dr. Bernhard Korte
Prof. Dr. Jens Vygen
Ulrich Brenner
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.
| Zeit, Ort | Mo 14-16 oder nach Vereinbarung, Institut für Diskrete Mathematik, Lennéstr. 2, Seminarraum |
| Vorbesprechung | Montag, den 10. Juli 2006 um 16 Uhr c.t. im Seminarraum des Institutes für Diskrete Mathematik, Lennéstraße 2 |
| Voraussetzungen | Vordiplom und mindestens eine Vorlesung (besser mehrere) aus dem Bereich der Diskreten Mathematik oder Mathematischen Optimierung. |
| Bereich (alte DPO) | A |
| Bereich (neue DPO) | A |
| Email-Kontakt | brenner@or.uni-bonn.de |
| Informationen im WWW | http://www.or.uni-bonn.de/lectures/ws06/sem_ws06.html |
|
Übersicht: alle Semester
Seminar Technische Neuroinformatik
Praktikum Mobile Roboter