Willkommen zum Hauptseminar Kombinatorische Optimierung
Inhalt
In der kombinatorischen Optimierung geht es darum, aus einer Menge von diskreten Objekten eine Teilmenge zu konstruieren, die gewissen Nebenbedingungen genügt und zusätzlich bezüglich einer gegebenen Kostenfunktion optimal ist. Die Hauptschwierigkeit ergibt sich aus der Tatsache dass die gegebenen Objekte nicht zerteilt werden können, also die gesuchten Lösungen bestimmte Ganzzahligkeitsbedinungen erfüllen müssen. Derartige Fragestellungen spielen in der Praxis eine grosse Rolle. In diesem Seminar werden einige prominente solche Probleme behandelt, und verschiedene effiziente Lösungsansätze vorgestellt.Termine
Das Seminar findet Donnerstags von 10-12 Uhr in HS B 251 statt. Erster Termin: Do 16.04.2015. An diesem Tag findet nach einer Einfürung die Themenvergabe statt.Am 14.5. und am 4.6. fällt das Seminar aus (Feiertage). Die Ausweichtermine sind jeweils am 13.5. und am 3.6., 10 - 12 Uhr, Raum C 112.
Wichtig: Alle Teilnehmer, die Ihre Leistung anrechnen möchten, werden gebeten, an Prof. Panagiotou eine Email mit folgendem Inhalt zu schreiben: Name, Matrikelnummer, Titel und Datum des Vortrags, Anrechnung für (Bachelor oder Master 3/6 ECTS, Modul), evtl. Anlagen (zB Ausarbeitung).
Literatur
- Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics), von Bernhard Korte, Jens Vygen
- M. Mezard, A. Montanari. Information, Physics and Computation, Oxford University press, 2009. Link zum Buch. Part D ist relevant für das Thema über Belief Propagation.