19234401
Lecture
WiSe 23/24: Diskrete Mathematik II - Optimierung
Ralf Borndörfer
Additional information / Pre-requisites
Credit
This course can be chosen as Discrete Mathematics II (DM II).
If Discrete Mathematics II - Extreme Combinatorics is taken at the same time, one of the two courses can be chosen as DM II and the other as a supplementary module.
Language
This lecture is in English.
close
Comments
This lecture starts the optimization branch of discrete mathematics. It deals with algorithmic graph theory and linear optimization.
Contents
Complexity: complexity measures, run time of algorithms, the classes P and NP, NP-completeness
Matroids and Independence Systems: independence systems, matroids, trees, forests, oracles, optimization over independence systems
Shortest Paths: nonnegative weights, general weights, all pairs
Network Flows: Max-Flow-Min-Cut Theorem, augmenting Paths, minimum cost flows, transport and allocation problems
Polyhedra: faces, dimension formula, projections of polyhedra, transformation, polarity, representation theorems
Foundations of linear optimization: Farkas Lemma, Duality Theorem
Simplex algorithm: basis, degeneration, basis exchange, revised simplex algorithm, bounds, dual simplex algorithm, post-optimization, numerics
Interior points and ellipsoid method: basics
Audience
This course is aimed at mathematics students with previous knowledge of discrete mathematics, linear algebra and analysis. Some exercises require the use of a computer.
close
Suggested reading
M. Grötschel, Lineare Optimierung, one of the scripts
V. Chvátal, Linear Programming, Freeman 1983
Additional
Garey&Johnson, Computers and Intractability, 1979 (Complexity Theory)
Bertsimas&Tsitsiklis, Introduction to Linear Optimization, 97 (Linear Programming)
Korte&Vygen, Combinatorial Optimization, 2006 (Flows, Shortest Paths, Matchings)
close31 Class schedule
Additional appointments
Wed, 2024-02-14 14:00 - 16:00Klausur
Wed, 2024-04-10 09:30 - 12:00
Nachklausur
Regular appointments
Mon, 2023-10-16 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-10-23 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-10-30 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-11-06 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-11-13 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-11-20 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-11-27 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-12-04 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-12-11 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2023-12-18 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2024-01-08 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2024-01-15 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2024-01-22 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2024-01-29 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2024-02-05 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Mon, 2024-02-12 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 1)
Wed, 2023-10-18 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-10-25 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-11-01 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-11-08 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-11-15 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-11-22 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-11-29 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-12-06 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-12-13 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2023-12-20 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2024-01-10 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2024-01-17 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2024-01-24 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2024-01-31 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)
Wed, 2024-02-07 14:00 - 16:00
Diskrete Mathematik II - Optimierung (Serientermin 2)