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