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 |