Forschungsgebiete
Kombinatorische und Diskrete Optimierung
In der kombinatorischen Optimierung beschäftigt man sich mit Lösungsverfahren für Probleme, die in der Regel eine problemspezifische kombinatorische Struktur der Lösungsmenge aufweisen. Ein klassisches Beispiel ist das Kürzeste Wege Problem. Hier ist ein Graph gegeben und die Lösungsmenge ist implizit durch die Menge von Wegen, die einen vorgegeben Startknoten mit einem Endknoten verbinden, beschrieben. Häufig sind die jeweiligen Optimierungsprobleme durch eine konkrete Anwendung aus der Praxis motiviert.
In der Arbeitsgruppe forschen wir sowohl an exakten, als auch an approximativen Verfahren, die in Polynomialzeit optimale Lösungen bzw. solche mit einer garantierten Güte berechnen.
Algorithmische Spieltheorie
Die nichtkooperative und kooperative Spieltheorie bieten mathematische Beschreibungen von dezentral organisierten Systemen an (z. B. Verkehrssysteme und das Internet); ein fundamentales Konzept der nichtkooperativen Spieltheorie ist z. B. das sogenannte Nashgleichgewicht. Ein zentraler Forschungsschwerpunkt der Arbeitsgruppe ist eine algorithmische Sicht auf die Themenkomplexe Existenz von Gleichgewichten, Berechnungskomplexität von Gleichgewichten und Qualität von Gleichgewichten
Bilevel Optimierung
Eine Optimierung von Systemen, die durch Gleichgewichtsbedingungen charakterisiert sind, fällt in das Gebiet der bilevel Optimierung. Probleme dieser Klasse sind recht schwierig zu lösen, da sie in der Regel nicht-konvex und auch nicht-differenzierbar sind. In diesem Bereich wird an den Themen Optimales Netzwerkdesign unter Gleichgewichtsbedingungen, Design von kombinatorischen Auktionen und Design von optimalen Kostenverteilungen in Netzwerken gearbeitet. Insbesondere wird in der Arbeitsgruppe an der Optimierung von Ampelschaltungen, dem Einsatz von Navigationsgeräten und an einer optimalen Netzplanung (unter Berücksichtigung von Nutzergleichgewichten) gearbeitet.