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.

### Contents

1. Coding length and the ellipsoid method
2. Simple polytopes and their graphs
3. The Hirsch conjecture and its refutation by Santos
4. Pivoting, Klee-Minty cubes etc
5. Random linear programs and average case analysis
6. Central paths, the interior point method and tropical linear programming

### Log-barrier interior point methods are not strongly polynomial

Presentation given 20 Oct 2017 at Bridging Continuous and Discrete Optimization, Simons Institute, Berkeley [pdf].

### polymake snippets

• basic linear programming: ipynb + pdf
• Paco's ipynb from 29 November 2019
• Sharir's Cube (construction by Günter M. Ziegler): poly pdf
• in polymake use `fan::planar_net(\$P)->VISUAL->FLAPS` produce a planar net of the polytope `\$P`

### References

1. Allamigeon, Xavier; Benchimol, Pascal; Gaubert, Stéphane; Joswig, Michael: Log-barrier interior point methods are not strongly polynomial. SIAM J. Appl. Algebra Geom. 2 (2018), no. 1, 140–178.
2. Blind, Roswitha; Mani-Levitska, Peter: Puzzles and polytope isomorphisms. Aequationes Math. 34 (1987), no. 2-3, 287–297.
3. Borgwardt, Karl-Heinz: The simplex method. A probabilistic analysis. Algorithms and Combinatorics: Study and Research Texts, 1. Springer-Verlag, Berlin, 1987.
4. Criado, Francisco; Santos, Francisco: Topological Prismatoids and Small Non-Hirsch Spheres, arXiv:1807.03030.
5. Dadush, Daniel; Huiberts, Sophie: A friendly smoothed analysis of the simplex method. STOC'18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 390–403, ACM, New York, 2018.
6. Even, Guy; Zadorojniy, Alexander: Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks. Ann. Oper. Res. 201 (2012), 159–167.
7. Friedman, Eric J.: Finding a simple polytope from its graph in polynomial time. Discrete Comput. Geom. 41 (2009), no. 2, 249–256.
8. Gärtner, Bernd; Henk, Martin; Ziegler, Günter M.: Randomized simplex algorithms on Klee-Minty cubes. Combinatorica 18 (1998), no. 3, 349–372.
9. Grötschel, Martin; Lovász, László; Schrijver, Alexander: Geometric algorithms and combinatorial optimization. Second edition. Algorithms and Combinatorics, 2. Springer-Verlag, Berlin, 1993.
10. 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.
11. Joswig, Michael; Theobald, Thorsten: Polyhedral and algebraic methods in computational geometry.
12. Joswig, Michael; Kaibel, Volker; Körner, Friederike: On the k-systems of a simple polytope. Israel J. Math. 129 (2002), 109–117.
13. Joswig, Michael; Ziegler, Günter M.: Neighborly cubical polytopes. Discrete Comput. Geom. 24 (2000), no. 2-3, 325–344.
14. Kaibel, Volker; Schwartz, Alexander: On the complexity of polytope isomorphism problems. Graphs Combin. 19 (2003), no. 2, 215–230.
15. Kalai, Gil: A simple way to tell a simple polytope from its graph. Journal of Combinatorial Theory, Series A 49 (1988), 381–383.
16. Kalai, Gil: Linear programming, the simplex algorithm and simple polytopes. Lectures on mathematical programming (ismp97) (Lausanne, 1997). Math. Programming 79 (1997), no. 1-3, Ser. B, 217–233.
17. Kim, Edward D.; Santos, Francisco: An update on the Hirsch conjecture. Jahresber. Dtsch. Math.-Ver. 112 (2010), no. 2, 73–98.
18. Matoušek, Jiří: Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Universitext. Springer-Verlag, Berlin, 2003.
19. Pach, János; Agarwal, Pankaj K.: Combinatorial geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1995.
20. Renegar, James: A mathematical view of interior-point methods in convex optimization. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2001
21. Santos, Francisco: A counterexample to the Hirsch conjecture. Ann. of Math. (2) 176 (2012), no. 1, 383–412.
22. Schrijver, Alexander: Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1986.
23. Springborn, Boris A.: A unique representation of polyhedral types. Centering via Möbius transformations. Math. Z. 249 (2005), no. 3, 513–517.
24. Wright, Stephen J.: Primal-dual interior-point methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.
25. Ziegler, Günter M.: Lectures on polytopes. Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995.