Die vier Kennzeichen eines kombinatorischen Optimierungsproblems
Warum Approximationsalgorithmen (polynomielle Laufzeit, Beziehung zu optimaler Lösung)
TSP mit den vier Kennzeichen beschreiben
Erklärung, warum TSP nicht mit relativer Güte approximiert werden kann (Reduktion von Hamilton-Kreis auf TSP, Gedankengang der Reduktion beschreiben)
Erläuterung vom metrischen TSP anhand der vier Kennzeichen
Christofides Algorithmus erklären und Analyse durchführen
In der Übung besprochene Alternative zu Christofides vorstellen (Verdopplung der Kanten statt leichtestes Matching, analysieren und Zeugen angeben)
Insgesamt eine gute Prüfungsatmosphäre und es gibt Hilfestellungen, wenn man mal nicht weiter kommt.