Discrete Mathematics II - Optimization
Ralf Borndörfer
Additional information / Pre-requisites
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.
closeComments
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.
closeSuggested 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)
close31 Class schedule
Regular appointments