WiSe 21/22: Discrete Mathematics II - Optimization
Ralf Borndörfer
Additional information / Pre-requisites
Credits
This course can be chosen as Discrete Mathematics II (DM II).
If you are taking Discrete Mathematics II - Extremal Combinatorics at the same time, you can choose one of the two courses as DM II and the other as a supplementary module (Ergänzungsmodul).
Language
This lecture is in English.
closeComments
This lecture starts the optimization branch of discrete mathematics. It deals with algorithmic graph theory and linear optimization.
Content
- Complexity: Complexity measures, runtime of algorithms, the classes P and NP, NP-completeness
- Matroids and independence systems: independence systems, matroids, trees, forests, oracles, optimization via independence systems
- Shortest paths: non-negative weights, general weights, all pairs
- Network flows: max-flow-min-cut theorem, augmenting paths, minimum cost flows, transportation and assignment problems
- Polyhedra: faces, dimensional formula, projections of polyhedra, transformation, polarity, representation
- Basics of linear optimization: Farkas lemma, duality theorem
- Simplex algorithm: basis, degeneration, basis exchange, revised simplex algorithm, bounds, dual simplex algorithm, post-optimization, numerics
- Inner Points and Ellipsoid Method: foundations
Target group
The lecture is for mathematics students with knowledge of discrete mathematics, linear algebra, and analysis. Some exercises require the use of a computer.
closeSuggested reading
M. Grötschel, Lineare Optimierung, eines der Vorlesungsskripte
V. Chvátal, Linear Programming, Freeman 1983
close
32 Class schedule
Additional appointments
Thu, 2022-02-24 09:30 - 12:30
Location:
0.3.12 Großer Hörsaal (Arnimallee 14)
Regular appointments