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.
Exam
The exam takes place at the last lecture. The 2nd exam takes place in the last week of the summer holidays before the lectures resume.
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 point and ellipsoid method: basics
Audience
This course is aimed at mathematics students with knowledge of discrete mathematics I, linear algebra and analysis. Some exercises require the use of a computer.
Suggested reading
M. Grötschel, Lineare Optimierung, eines der Vorlesungsskripte
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)
31 Class schedule
Regular appointments
Thu, 2025-10-16 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-10-23 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-10-30 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-11-06 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-11-13 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-11-20 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-11-27 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-12-04 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-12-11 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2025-12-18 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2026-01-08 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2026-01-15 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2026-01-22 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2026-01-29 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2026-02-05 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Thu, 2026-02-12 12:00 - 14:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A7/SR 031 (Arnimallee 7)
Mon, 2025-10-20 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Mon, 2025-10-27 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2025-11-03 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2025-11-10 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2025-11-17 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2025-11-24 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2025-12-01 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2025-12-08 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2025-12-15 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2026-01-05 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2026-01-12 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2026-01-19 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2026-01-26 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2026-02-02 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
Mon, 2026-02-09 14:00 - 16:00
Diskrete Mathematik II - Optimierung
Lecturers:
Univ.-Prof. Dr. Ralf Borndörfer
Location:
A6/SR 032 Seminarraum (Arnimallee 6)
