Topics

• Algorithms (Sorting, Dijkstra, TSP, Maximum Matchings, Certificates (Tutte's Theorem), Network Flows and their applications (Menger's Theorem, Baranyai's Theorem), Stable Matching and their applications (List Colorings))
• Linear Programming (Simplex Algorithm), Duality and their applications in combinatorics and algorithms
• Randomized Algorithms (randomized matching algorithms, hypergraph-coloring, derandomization, Erdos-Selfridge Criterion, algorithmization of Local Lemma)

Further impressions about the course material can be gained through the website of an earlier edition: http://discretemath.imp.fu-berlin.de/DMII-2018-19/

Contact

Tibor Szabó: szabo@zedat.fu-berlin.de
Silas Rathke: s.rathke@fu-berlin.de

Exams

The exams will take place on the following dates:

• 2nd of March, 10am - 1pm, Hörsaal A, Arnimallee 22
  • Post-Exam Review: 8th of March, 2pm - 3pm,
• 13th of April, 10am - 1pm, Großer Hörsaal, Takustraße 9
  • Post-Exam Review: 24th of April, 2pm-3pm

Literature

• 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