Inhalt

Die Vorlesung wird die folgenden drei Themenblöcke umfassen:

• IP in fester Dimension
• Polytope und der Simplex-Algorithmus
• Erweiterte Formulierungen

Termine

Vorlesung (Prof. V. Kaibel); Eintrag im LSF

• Mo, 13:15-14:45, G03-214
• Di, 15:15-16:45, G03-214

Übung (Prof. V. Kaibel); Eintrag im LSF

• Do, 07:30-09:00, G03-214

(Campus-Plan)

Vorlesungsanschriebe

Ich werde statt der Kreidetafel ein Tablet und einen Beamer benutzen. Die Anschriebe stelle ich im Anschluss an jede Vorlesung hier als PDF-Damtei zur Verfügung.

• VL 01 (14.10.19)
• VL 02 (15.10.19)
• VL 03 (17.10.19)
• VL 04 (21.10.19)
• VL 05 (22.10.19)
• VL 06 (28.10.19)
• VL 07 (29.10.19)
• VL 08 (05.11.19)
• VL 09 (11.11.19)
• VL 10 (12.11.19)
• VL 11 (18.11.19)
• VL 12 (25.11.19)
• VL 13 (26.11.19)
• VL 14 (02.12.19)
• VL 15 (03.12.19)
• VL 16 (09.12.19)
• VL 17 (16.12.19)
• VL 18 (17.12.19)
• VL 19 (13.01.20)
• VL 20 (14.01.20)
• VL 21 (20.01.20)
• VL 22 (21.01.20) (Vorsion korrigiert am 28.2.2020)
• VL 23 (27.01.20)
• VL 24 (28.01.20)
  Folien zum Correlation Polytop

Zusatzmaterial zu unteren Schranken an die Erweiterungskomplexität

• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
  Samuel Fiorini, Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis
  In: Discrete Math., 2013, 313 (1), 67-83 (pdf)
• A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially
  Volker Kaibel, Stefan Weltge
  In: Discrete & Computational Geometry, 2015, 53 (2), 396--401 (pdf)

Übungsblätter

• 1. Übungsblatt (Besprechung am 24.10.)
  Lösungsskizze Aufgabe 3
• 2. Übungsblatt (Besprechung am 14.11.)
• 3. Übungsblatt (Besprechung am 19.12.)

Leseaufgaben

• Für den 7. November
  Deciding whether a Lattice has an Orthonormal Basis is in co-NP
  (Christoph Hunkenschröder, arXiv:1910.03838, Oktober 2019)
  Leitfragen:
  • Was ist das Hauptresultat der Arbeit?
  • Was ist das Unimodular Decomposition Problem und in welcher Beziehung steht es zum Hauptresultat?
  • Welche Rolle spielt das Theorem von Elkies, das in der Arbeit verwendet wird?
• Für den 28. November / 5. Dezember / 12. Dezember
  Complexity and Algorithms for Computing Voronoi Cells of Lattices
  (Matthieu Dutour Sikirić, Achill Schürmann und Frank Vallentin, Mathematics of Computation 78, 267 (2009), 1713–1731)
  Leitfragen:
  • Welcher (kleine) Teil der Arbeit beschäftigt sich mit dem Gitter-Isomorphie Problem?
  • Wie funktioniert die Reduktion des Graphen-Isomorphie Problems auf das Gitter-Isomorphie Problem?
  • Welches Theorem von Whitney wird wie benutzt?
  Hier finden Sie Whitney's Theorem.
  Anschriebe:
  • Reading Course 28.11.19
  • Reading Course 5.12.19
• Für 16., 23. und 30. Januar
  Die Sherali-Adams Hierarchie
  (Conforti, Cornuejols, Zambelli: Integer Programming, Springer 2014, Kapitel 10.4.1)
  Leitfrage:
  • Warum ist das n-te Level der Sherali-Adams Hierarchie gleich der ganzzahligen Hülle?
  Anschriebe:
  • Reading Course 16.01.20
  • Reading Course 23.01.20
  • Reading Course 30.01.20

Prüfung / Leistungsnachweis

Für die Prüfung empfehlen wir Ihnen, sich neben dem Vorlesungsstoff mit allen Übungsblättern und den Leseaufgaben ausgiebig zu beschäftigen.

Für einen Leistungsnachweis wird es am Ende des Semesters Gekegenheit zu einem Scheingespräch geben.