This course is the third and last in the sequence "Algorithmic Discrete Mathematics". It is meant for, but not restricted to, students in mathematics with an interest in a Master's Thesis (in discrete optimization and related areas) and PhD students of the BMS. The course takes place on Tuesdays and Thursdays, 10-12, in MA 550 at TU Berlin. It counts as a BMS Advanced Course.

The topic of the course is the complexity of linear programming. While results exist in abundance, the precise status is still unsettled. In fact, this is number 9 on Smale's list of mathematical problems for the 21st century.

The lecture on Tuesday, 27 Nov 2019 featured presentations by OSCAR developers.

- Coding length and the ellipsoid method
- Simple polytopes and their graphs
- The Hirsch conjecture and its refutation by Santos
- Pivoting, Klee-Minty cubes etc
- Random linear programs and average case analysis
- Smoothed analysis
- Central paths and the interior point method
- Tropical linear programming

18 October 2018, 23 October 2018, 25 October 2018, 06 November 2018, 13 November 2018

Exercises 1: 8 November 2018, Exercises 2: 22 November 2018, Exercises 3: 13 December 2018

- Blind, Roswitha; Mani-Levitska, Peter: Puzzles and polytope isomorphisms. Aequationes Math. 34 (1987), no. 2-3, 287–297.
- Criado, Francisco; Santos, Francisco: Topological Prismatoids and Small Non-Hirsch Spheres, arXiv:1807.03030.
- Grötschel, Martin; Lovász, László; Schrijver, Alexander: Geometric algorithms and combinatorial optimization. Second edition. Algorithms and Combinatorics, 2. Springer-Verlag, Berlin, 1993.
- Friedman, Eric J.: Finding a simple polytope from its graph in polynomial time. Discrete Comput. Geom. 41 (2009), no. 2, 249–256.
- Grünbaum, Branko: Convex polytopes. Second edition. Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler. Graduate Texts in Mathematics, 221. Springer-Verlag, New York, 2003.
- Joswig, Michael; Theobald, Thorsten: Polyhedral and algebraic methods in computational geometry.
- Joswig, Michael; Kaibel, Volker; Körner, Friederike: On the k-systems of a simple polytope. Israel J. Math. 129 (2002), 109–117.
- Joswig, Michael; Ziegler, Günter M.: Neighborly cubical polytopes. Discrete Comput. Geom. 24 (2000), no. 2-3, 325–344.
- Kaibel, Volker; Schwartz, Alexander: On the complexity of polytope isomorphism problems. Graphs Combin. 19 (2003), no. 2, 215–230.
- Kalai, Gil: A simple way to tell a simple polytope from its graph. Journal of Combinatorial Theory, Series A 49 (1988), 381–383.
- Kim, Edward D.; Santos, Francisco: An update on the Hirsch conjecture. Jahresber. Dtsch. Math.-Ver. 112 (2010), no. 2, 73–98.
- Matoušek, Jiří: Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Universitext. Springer-Verlag, Berlin, 2003.
- Pach, János; Agarwal, Pankaj K.: Combinatorial geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1995.
- Santos, Francisco: A counterexample to the Hirsch conjecture. Ann. of Math. (2) 176 (2012), no. 1, 383–412.
- Schrijver, Alexander: Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1986.
- Springborn, Boris A.: A unique representation of polyhedral types. Centering via Möbius transformations. Math. Z. 249 (2005), no. 3, 513–517.
- Ziegler, Günter M.: Lectures on polytopes. Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995.