Advanced Topics in Linear and Discrete Optimization (ADM III)

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 (tentative)

  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. Smoothed analysis
  7. Central paths and the interior point method
  8. Tropical linear programming

Notes

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

Exercises

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

polymake snippets

References (to be extended)

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

Home Teaching Presentations Projects Software

Last modified: Wed Dec 12 10:06:40 UTC 2018 by joswig