Themen des Kurses

• Algorithmen (Sortierung, Dijkstra, TSP, Maximum Matchings, Zertifikate (Tutte's Theorem), Netzwerkflüsse und ihre Anwendungen (Menger's Theorem, Baranyai's Theorem), Stable Matching und seine Anwendung (Listenfärbung))
• Lineare Programmierung (Simplex Algorithmus), Dualität und ihre Anwendungen in der Kombinatorik und Algorithmen
• Randomisierte Algorithmen (randomisierte Matching Algorithmen, hypergraph-coloring, derandomization, Erdos-Selfridge Criterion, algorithmization of Local Lemma)

Weitere Informationen über den Kurs werden auf der Kurswebsite verfügbar sein: http://discretemath.imp.fu-berlin.de/DMII-2020-21

Literatur

• L. Lovász, J. Pelikán, K. Vesztergombi, Discrete Mathematics
• J. Matousek - B. Gaertner, Understanding and Using Linear Programming
• D. West, Introduction to Graph Theory

Further reading:

• V. Chvátal, Linear Programming.
• Schrijver, Theory of Linear and Integer Programming
• Schrijver, Combinatorial Optimization