Seminar Sommer 2006:
Kombinatorische
Optimierung
| Blockseminar am Ende des Semesters |
|
| |
|
| Vorbesprechung: Dienstag 4. April, 14:00, OH 14, Raum 304 | |
| |
|
Inhalte:
Kombinatorische
Optimierungsprobleme sind heutzutage allgegenwärtig. Die
Fähigkeit Optimierungsprobleme schnell und zuverlässig
lösen zu können ist daher oft ein Wettbewerbsvorteil.
Ein wichtiger Ansatz hierzu ist die lineare und ganzzahlige
Programmierung im Zusammenspiel mit der so genannten
polyedrischen Kombinatorik. In diesem Seminar werden wir in das
faszinierende Gebiet der kombinatorischen Optimierung eintauchen und
dort insbesondere die polyedrischen Methoden kennen lernen. Wir
besprechen das Buch Combinatorial
Optimization, Theory and Algorithms von Bernhard Korte und Jens Vygen,
welches im Springer Verlag erschienen ist.
Themen:
Lineare Programmierung
Ellipsoid Methode und
Äquivalenz von Separierung und Optimierung
Ganzzahlige Programmierung
Spannbäume und
Arboresences
Netzwerk Flüsse,
(s,t)-Flüsse
Gomory-Hu Bäume
Mincost
Network Flows
Matching,
Edmonds Algorithmus
Matroide
und Greedy Algorithmus
Knapsack
und Bin Packing
Fraktionale
Mehrgüterflüsse