Seminar Optimierung

Henning Bruhn-Fujimoto und Laura Gellert


Ort: HeHo18 E60 ( außer am 23. Oktober: O28/2001)
Zeit: Donnerstag 12-14 Uhr

Themen:
In dem Seminar behandeln wir Themen, die die Vorlesung Optimierung / OR 1 ergänzen. Dabei sollen sich die Teilnehmer ausgewählte Inhalte aus dem Buch "Exact Exponential Algorithms" von Fomin und Kratsch selbstständig erarbeiten und dann in geeigneter Form präsentieren.

 

1) Branching (P. Ekmekci, 23.10.14)
Kap. 1.3 branching algorithm for independent set
Kap. 2.1 fundamentals, branching vectors

2) Branching (M. Heinlein, 30.10.14)
Kap. 2.2 k-SAT

3) Dynamic Programming  (S. Steinacher, 6.11.2014)
Kap. 3.1.1 Permutation problems: scheduling
Kap. 3.1.2 Partition problems: graph colouring 

4) Inclusion-Exclusion (M. Baier, 20.11.2014)
Kap. 4.1 Inclusion-Exclusion Principle
Kap. 4.2.3 Bin packing

5) Treewidth (S. Urbon, 27.11.2014)
Kap 5.1 fundamentals, MaxCut and/or perfect matchings

6) Measure and Conquer (S. Kunzweiler, 4.12.2014)
Kap. 6.1 Independent Set

7) Split and List (P. Schaumann, 11.12.2014 )
Kap. 9.1 Sort and Search: 2-Table und binary knapsack
Kap. 9.2 Maximum Cut