Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum Diskrete Optimierung (Modul P2C1)
Frühjahr 2009
Thema: Min-Cost-Flow-Algorithmen
Ein grundlegendes kombinatorisches Optimierungsproblem ist das
Minimum-Cost-Flow-Problem.
Es tritt in zahlreichen Anwendungen auf, so z.B. in der
Placement-Legalisierung von Chips.
Wir werden verschiedene Algorithmen für das Minimum-Cost-Flow-Problem
implementieren.
Wegen der großen Instanzen wird auf Effizienz großer Wert gelegt.
Bevorzugte Programmiersprache ist C++.
Teilnahmevoraussetzung ist das Modul "Einführung in die Diskrete
Mathematik".
In dieser Vorlesung werden die theoretischen Grundlagen behandelt.
Da das Praktikum im Frühjahr 2009 stattfindet, kann diese
Voraussetzung auch noch im WS 08/09 erworben werden.
Die Veranstaltung richtet sich an Studentinnen und Studenten sowohl
der Informatik
als auch der Mathematik. In jedem Fall wird aber ein hohes
mathematisches Interesse
vorausgesetzt. Grundlegende Programmierkenntnisse werden ebenfalls vorausgesetzt.
Links:
Themen und Teilnehmer:
- Minimum-Mean-Cycle-Cancelling-Algorithmus: Shoshanna Seenberg, Maxim Janzen
Erste Besprechung: 9.3.2009, 15:00 Uhr
- Orlins Algorithmus: Lars Torge Jensen, Philipp Ochsendorf
Erste Besprechung: 5.3.2009, 14:00 Uhr
- Cost-Scaling-Algorithmus: Lars Bellinghausen, Cornelius Dirk
Erste Besprechung: 10.3.2009, 14:00 Uhr
- Forest-Cut-Algorithmus: Kai Gödde, Alfredo Giugliano Wutschka
Erste Besprechung: 9.3.2009, 10:00 Uhr
Prof. Dr.
B. Korte,
Prof. Dr.
J. Vygen,
Prof.
Dr. S. Hougardy,
Jun.Prof.
Dr. T. Nieberg,
Dr. U.
Brenner