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 overe independence systems, greedy algorithm, Edmonds-Rado Theorem
• Shortest Paths: non-negative weights, potentials, Dijkstra and A* algorithms, general weights, Moore-Bellman-Ford algorithm, minimum mean cycle algorithm, all pairs, Floyd-Warshall algorithm 
• Maximum Flows: max flow problem, max-flow-min-cut Theorem, augmenting paths, Ford-Fulkerson and Edmonds-Karp algorithm, flow decompostion and Menger Theorems
• Minimum Cost Flows: minimum mean cycle cancelling algorithm, successive shortest path algorithm, transportation and assignment problems
• Matchings: Hopcroft-Karp and Edmond's blossom shrinking algorithms
• Linear Programs: inequality systems, standard form, transformations, dual LP, Duality Theorem, complementary slackness, geometry of LPs, combinatorial LPs
• Polyhedra and Polytopes: Minkowski sum, linear, affine, convex, conic combinations, hyperplanes and halfspaces, dimension, projections of polyhedra, Fourier-Motzkin elimination
• Alternative Theorems: Farkas Lemma
• Simplex Algorithm: basis, reduced costs, pivot, tableau, optimality criterion, dual solution, revised simplex method, degeneracy, cycling, pivot rules, worst case complexity, phase I/II, dual simplex algorithm, sensitivity and post optimization
• Polyhedral Theory: polar, homogenization, representation Theorems of Weyl and Minkowski, valid and supporting inequaliteis, gamma polar, faces, interior points, dimension formula, redundancy, facets, vertices, edges, extreme rays, extremals, pointed polyhedra, optimal LP vertices, basis of a cone/polytope/polyhedron, representation by few generators, Krein-Milman and Caratheodory Theorems
• Ellipsoid Method: complexity of vertices, minimum volume of polytopes, Löwner-John ellipsoid, polynomail equivalence of optimizuation and feasibility, complexity of linear programming
• Interior Point Methods: strict feasibility, primal-dual problem, KKT system, barrier functions and problems, central path, residau and duality gap, KKT solution by Newton's method, path following methods, complexity of path following methods

Target group

This lecture is intended for mathematics students with prior knowledge in Discrete Mathematics, Linear Algebgra, and Analysis. Some exercises might require the use of a computer.

Videos

Vidoes of the WS 2021 course of DM II (with indentical content) is available via the Vbrick Rev platform of FU. Here is the link to the DM II stream:

https://fu-berlin.eu.vbrickrev.com/#/playlist/4540300f-897f-4859-936c-2fd846816895/videos/ 

Literature