Lehrinhalte
Simplex-Verfahren: revidierter Simplex-Algorithmus, dualer Simplexalgorithmus Pivotregeln, exponentielle Beispiele Polyedertheorie, Geometrie des Simplex-Verfahrens Primal-duale Algorithmen mit Anwendungen bei Graphen und Netzwerken Polynomiale Verfahren: Ellipsoid-Methode, innere-Punkte-Verfahren
Ganzzahlige lineare Optimierung: Branch und Bound, Lagrange Relaxation, Schnittebenenverfahren
Zuordnungsprobleme,Matchings, Matroide
Polynomiale Techniken zur Behandlung NP-schwerer Probleme: Approximationsalgorithmen, Gutegarantien. Klassikation der Approximierbarkeit, stark- und schwach NP-vollstandig, MAX-SNP schwer.