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.

Contents (tentative)

  1. Coding length and the ellipsoid method
  2. Simple polytopes and their graphs
  3. Klee-Minty cubes and generalizations
  4. The Hirsch Conjecture and Santos' refutation
  5. Random linear programs and average case analysis
  6. Smoothed analysis
  7. Central paths and the interior point method
  8. Tropical linear programming

References (incomplete)

  1. Grötschel, Martin; Lovász, László; Schrijver, Alexander: Geometric algorithms and combinatorial optimization. Second edition. Algorithms and Combinatorics, 2. Springer-Verlag, Berlin, 1993. xii+362 pp. ISBN: 3-540-56740-2
  2. Joswig, Michael; Theobald, Thorsten: Polyhedral and algebraic methods in computational geometry. Revised and updated translation of the 2008 German original. Universitext. Springer, London, 2013. x+250 pp. ISBN: 978-1-4471-4816-6; 978-1-4471-4817-3
  3. Schrijver, Alexander: Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1986. xii+471 pp. ISBN: 0-471-90854-1
  4. Ziegler, Günter M.: Lectures on polytopes. Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995. x+370 pp. ISBN: 0-387-94365-X

Home Teaching Presentations Projects Software

Last modified: Tue Oct 16 12:02:19 UTC 2018 by joswig