Seminar Optimierung - Schwierige Probleme der kombinatorischen Optimierung (SoSe 2015)
Daten
Das Seminar wird durch
Prof. Volker Kaibel und
Stefan Weltge betreut.
Wir treffen uns wöchentlich donnerstags, 13:30-15:00 Uhr in G05-312.
Vortrag / Leistungsnachweis
Es wird erwartet, dass der ca. 60-minütige Vortrag von einer LaTeX-Beamer-Präsentation begleitet wird.
Für formale Beweise bietet es sich in der Regel an, diese an der Tafel vorzuführen.
Zudem soll eine schriftliche Zusammenfassung (eine Seite) des Vortragsthemas angefertigt werden und als Handout
zur Verfügung gestellt werden.
Termine
-
13.04. NP-schwierige Probleme (Prof. Kaibel)
Folien
-
23.04. Lösungsansätze für schwierige Probleme + Vorträge mit Beamer-LaTeX (Stefan Weltge)
Folien, LaTeX-Vorlage
-
30.04. Die Held-Karp-Relaxierung für das TSP (DE)
Quellen: Korte & Vygen (2012), Abschnitte 21.5, 5.6
Betreuer: Weltge
-
07.05. Das TSP-Polytop (SG)
Quellen: Korte & Vygen (2012), Abschnitte 21.4, 12.4
Betreuer: Kaibel
-
21.05. LP-Relaxierungen für das Steinerbaum-Problem (PB)
Quellen: Goemans
& Myung,
evt. Koch & Martin
Betreuer: Weltge
-
28.05. Deterministisches Runden von LPs (Scheduling, Facility Location, Bin-Packing)
(DDL)
Quellen: Williamson & Shmoys, Kapitel 4
Betreuer: Kaibel
-
04.06. Randomisiertes Runden von LPs (PP)
Quellen: Williamson & Shmoys, Kapitel 5
Betreuer: Kaibel
-
11.06. Randomisiertes Runden von SDPs (JF)
Quellen: Williamson & Shmoys, Kapitel 6
Betreuer: Kaibel
-
18.06. Das Färbungsproblem (TS)
Quellen: Sharma & Chaudhari, Section 3.1;
Garey &, Johnson, Theorem 4.2
Betreuer: Weltge
-
25.06. Der Theta-Körper (JK)
Quellen: Conforti, Cornuéjols & Zambelli, Section 10.2.2;
Knuth, Sections 31 & 32
Betreuer: Weltge
-
02.07. Stabile Mengen und quadratische Optimierung über Simplizes (AK)
Quellen: Gibbons, Hearn, Pardalos & Ramana
Betreuer: Kaibel
-
09.07. Primal-duale Approximationsalgorithmen (MM)
Quellen: Williamson & Shmoys, Kapitel 7
Betreuer: Weltge