RUB » LMI » Lehre » Proseminar über submodulare Funktionen und Optimierung SS 2014

Proseminar über submodulare Funktionen und Optimierung SS 2014

LVR-Nr: 150 419
Veranstaltung: Proseminar über submodulare Funktionen und Optimierung
Mo 16.15 - 17.45, NA 4/64
Hinweis: Alle Vortragstermine sind bereits belegt.
Daher sind keine weiteren Anmeldungen möglich.
Dozent: Hans U. Simon

Kommentar

Submodularität spielt bei diskreten Strukturen eine ähnliche Rolle wie Konvexität in der Analysis. Im Proseminar behandeln wir die grundlegende Theorie der submodularen Funktionen und lernen effiziente Algorithmen zur Minimierung derselben kennen. Zudem wird deutlich werden, welche Optimierungsprobleme sich mit Hilfe submodularer Funktionen beschreiben lassen.

Bedingungen für den Erhalt des Proseminarscheins sind regelmäßige Teilnahme an den Seminarsitzungen sowie ein erfolgreicher Vortrag .

Voraussetzungen

Eine Voraussetzung zur Teilnahme am Proseminar ist die erfolgreiche Absolvierung der mathematischen Grundvorlesungen des ersten Studienjahres.

Literatur

Das Seminar orientiert sich hauptsächlich an dem ersten der folgenden beiden Bücher (insbesondere Kapitel 3, 13, 14). Das zweite Buch rangiert unter weiterführende Literatur.:

Buch 1
Bernhard Korte und Jens Vygen, "Kombinatorische Optmierung"
Buch 2
Satoru Fujishige, "Submodular Functions and Optimization"

Die zwei Bücher stehen ab sofort in der Mathe-Bibliothek als Präsenzexemplare zur Verfügung.

Zeitplan

07.04.2014 Buch 1, Kap. 3.1-3.3 Lineare Programmierung und der Simplex-Algorithmus (Teil 1) Sven Graus und Niklas Schindler
14.04.2014 Buch 1, Kap. 3.1-3.3 Lineare Programmierung und der Simplex-Algorithmus (Teil 2) Sven Graus und Niklas Schindler
28.04.2014 Buch 1, Kap. 3.4, 3.5 Dualität, konvexe Huellen und Polytope Eva Moering
05.05.2014 Buch 1, Kap. 4.6 Reduktion des Optimierungsproblems auf das Separationsproblem Alina Kroppenberg
12.05.2014 Buch 1, Kap. 13.1-13.3 Grundlegende Matroideigenschaften und Dualität (Teil 1) Tim Niederberghaus und Frederik Wirth
19.05.2014 Buch 1, Kap. 13.1-13.3 Grundlegende Matroideigenschaften und Dualität (Teil 2) Tim Niederberghaus und Frederik Wirth
26.05.2014 Buch 1, Kap. 13.4 Der gierige Algorithmus Asja Fischer
02.06.2014 Buch 1, Kap. 13.5-13.7 Das Durchschnitts- und das Partitionierungsproblem fuer Matroide (Teil 1) Anne Bröckers und Isabel Horn
16.06.2014 Buch 1, Kap. 13.5-13.7 Das Durchschnitts- und das Partitionierungsproblem fuer Matroide (Teil 2) Anne Bröckers und Isabel Horn
23.06.2014 Buch 1, Kap. 14.1-14.3 Greedoide, Polymatroide und Minimierung submodularer Funktionen (Teil 1) Sebastian Gonzalez und Marilena Waldmeier
30.06.2014 Buch 1, Kap. 14.1-14.3 Greedoide, Polymatroide und Minimierung submodularer Funktionen (Teil 2) Sebastian Gonzalez und Marilena Waldmeier
07.07.2014 Buch 1, Kap. 14.4, 14.5 Schrijvers Algorithmus und symmetrische submodulare Funktionen Ivo Zabot