This lecture starts the optimization branch of discrete mathematics. It deals with algorithmic graph theory and linear optimization.

Content

1. Complexity: Complexity measures, runtime of algorithms, the classes P and NP, NP-completeness
2. Matroids and independence systems: independence systems, matroids, trees, forests, oracles, optimization via independence systems
3. Shortest paths: non-negative weights, general weights, all pairs
4. Network flows: max-flow-min-cut theorem, augmenting paths, minimum cost flows, transportation and assignment problems
5. Polyhedra: faces, dimensional formula, projections of polyhedra, transformation, polarity, representation
6. Basics of linear optimization: Farkas lemma, duality theorem
7. Simplex algorithm: basis, degeneration, basis exchange, revised simplex algorithm, bounds, dual simplex algorithm, post-optimization, numerics
8. 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.

M. Grötschel, Lineare Optimierung, eines der Vorlesungsskripte

V. Chvátal, Linear Programming, Freeman 1983

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.