Einführung in die Kombinatorische Optimierung

Themen:

• Lineare Optimierung: Polyeder und LP Dualität
• Komplexität von Algorithmen
• Polynomiale Algorithmen für 
  • Minimal aufspannende Bäume
  • kürzeste Wege
  • Maximalfluss und kostenminimale Flüsse
  • maximales Matching und ihr Bezug zur Linearen Programmierung
• Polyhedrale Kombinatorik zur Behandlung NP-schwerer Probleme (Knapsack, TSP, Clique Partioning)