Seminar Sommer 2006:

Kombinatorische Optimierung



Blockseminar am Ende des Semesters



Vorbesprechung: Dienstag 4. April,  14:00, OH 14, Raum 304






A coloring of a graph

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