Mathematics, Discrete Optimization

Discrete Optimization (ADM II)

Summer term 2021
Lecturer Max Klimm, Teaching Assistant Martin Knaack
Further information and learning material can be found on the ISIS page of this lecture

This lecture is the sequel to the lecture "Introduction to linear and combinatorial optimization (ADM I)". We cover advanced combinatorial and discrete optimization methods such as

  • Computation of maximal branchins
  • Computation of maximal matchings in general graphs
  • Computation of maximum weight matchings in general graphs
  • T-Joins and the postperson problem
  • Matroids and optimization on matroids
  • Compexity theory and NP-completeness
  • Integer linear programming
  • Travelling Salesperson Problem

Knowledge of a programming language (e.g. python) is desirable. Basic knowledge of calculus and linearer algebra and the succesfull completion of the lecture "Introduction to linear and combinatoral optimization (ADM I)" are helpful.