Discrete Optimization (ADM II)

Summer 2021
Lecturer: Max Klimm, Assistant: Martin Knaack
More information and materials: ISIS course page

Content

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

Prerequisites

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.