|
Lehrende: Dr. rer. nat. Andreas Paffenholz
Veranstaltungsart:
Vorlesung und Übung
Orga-Einheit: FB04 Mathematik
Anzeige im Stundenplan:
Geom Combinatorics
Fach:
Anrechenbar für:
Semesterwochenstunden:
3
Unterrichtssprache:
Deutsch und Englisch
Min. | Max. Teilnehmerzahl:
- | -
Lehrinhalte:
Wir wollen uns mit der Struktur von Gittern und Gitterpunkten in Polyedern sowie ihrer Beziehung zur Diskreten und Kombinatorischen Optimierung aus geometrischer Sicht beschäftigen.
Ein Gitter ist die Menge der Linearkombinationen mit ganzzahligen Koeffizienten einer linear unabhängigen Menge von Vektoren eines (endlichdimensionalen) Vektorraums. Ein bekanntes und wichtiges Beispiel ist das Gitter Zn der Punkte mit ganzzahligen Koordinaten. Eine zentrale Aufgabe in der ganzzahligen Optimierung ist zu entscheiden, ob ein Polyeder einen Punkt aus diesem Gitter enthält.
Ausgangspunkt der Vorlesung ist die Geometrie der Zahlen. Die grundlegenden Aussagen in diesem Gebiet beschäftigen sich mit Bedingungen, unter denen ein konvexer Körper einen Gitterpunkt enthält. Begründet wurde sie durch Minkowkis First Theorem, das zeigt, dass jeder zentralsymmetrische konvexe Körper mit ausreichend großem Volumen einen von Null verschiedenen Gitterpunkt enthält. Die entsprechende algorithmische Frage ist, ob und wie wir einen solchen Gitterpunkt finden können, wenn er existiert. Das Problem ist im allgemeinen in NP, aber wir werden einen Algorithmus kennenlernen, der in fester Dimension polynomiell ist. Er beruht auf einem Algorithmus zur Bestimmung kurzer Vektoren in einem Gitter und dem Flachheitssatz, der zeigt, dass konvexe Körper, die keinen Gitterpunkt enthalten, in ihrer Weite durch eine universelle, nur von der Dimension abhängige Schranke beschränkt sind. Anschließend wenden wir uns der Frage zu, wie wir Gitterpunkte in Polyedern zählen können. Das führt uns zur Ehrharttheorie und auf der algorithmischen Seite zum Algorithmus von Barvinok.
Themen der Vorlesung
- Gitter und Polyeder
- Geometrie der Zahlen, die Sätze von Minkowski und Blichfeldt
- Gitterreduktion und der LLL-Algorithmus
- Das Problem des kürzesten Vektors
- ganzzahlige Optimierung in fester Dimension mit Lenstras Algorithmus
- Rationale Erzeugendenfunktionen für Giterpunkte und der Algorithmus von Barvinok
Weitere Themen könnten, je nach verfügbarer Zeit, ggf. noch parametrische ganzzahlige Optimierung oder Schnitte und gitterfreie Polytope sein.
Literatur:
Dimitris Bertsimas und Robert Weismantel, Optimization over Integers, Dynamic Ideas, (2005).
Rekha Thomas, Lectures in geometric combinatorics, AMS (2005).
Alexander Barvinok, A Course in Convexity, AMS (2002)
Jesus De Loera, Raymond Hemmecke, Matthias Köppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization, SIAM (2012)
Voraussetzungen:
grundlegende Kenntnisse der Polyedertheorie, sowie der linearen und ganzzahligen Programmierung, wie sie z.B. in den Vorlesungen Einführung in die Optimierung und Diskrete Optimierung vermittelt werden. Fehlende Vorkenntnisse können ggf. im Rahmen der Vorlesung oder im Tutorium wiederholt werden.
Online-Angebote:
moodle
|
