Anders als Optimierung 1 konzentriert sich diese Vorlesung auf algorithmisch schwere Probleme, für die man keine Verfahren kennt, die sowohl effizient als auch exakt wären. Ausgehend von grundlegenden Überlegungen zur Komplexität (P/NP, NP-Vollständigkeit) werden vielfältige Methoden zur Entwicklung approximativer Verfahren vorgestellt. Die betrachteten Probleme (Set Cover, Knapsack, Bin Packing, Network Design, Traveling Salesman) unterscheiden sich in der Approximierbarkeit ganz erheblich. Während man für manche beliebige Genauigkeit und Effizienz gleichzeitig erzielen kann, sind für andere nur sehr schwache Gütegarantien beweisbar.

Turnus:  jedes Wintersemester

Diese Vorlesung führt die Graphentheorie aus dem Bachelor weiter und vertieft gezielt wechselnde aktuelle Themen des Gebietes. In den vergangenen Jahren wurden unter anderem folgende Themen behandelt:

• Färbungstheorie
• Graphenklassen
• Hypergraphen
• Gerichtete Graphen
• Probabilistische Methoden
• Algebraische Graphentheorie
• Extremale Graphentheorie
• Weiteparameter und Zerlegungen

Turnus:  jedes Sommersemester

Game theory is the study of multiperson decision problems. Such problems arise frequently in competitive scenarios where knowledge is distributed, such as in economics.  For instance, oligopolies incorporate multiperson problems: each one must consider what the others will do in order to achieve success in a competitive environment. In this course of game theory we study the elements of game theoretical models.

Turnus:  jedes Sommersemester

Es gibt eine Reihe weiterer möglicher Vorlesungen, die wir nach Interesse unregelmäßig anbieten. Hier einige Beispiele:

• Matroide und submodulare Funktionen
• Optimierung in der Praxis - Probleme des Chip Design
• Probabilistische Methoden
• Online and Distributed Algorithms