Diese Lehrveranstaltung befasst sich mit kombinatorischen Optimierungsproblemen die in der LV 'Kombinatorische Optimierung 1' nicht behandelt wurden. In der Regel sind das NP-schwere Optimierungsprobleme für die sowohl strukturelle Eigenschaften als auch Lösungsansätze besprochen werden. Je nach Problem wir ein breiter Bogen gespannt: von Schranken und Heuristiken bis hin zu Approximationsalgorithmen, PTAS und FPTAS. Das Ziel ist, einerseits die Studierenden mit prominenten, sowohl theoretisch als auch praktisch relevanten Problemen der Kombinatorischen Optimierung vertraut zu machen, und anderseits eine Handvoll an Lösungsansätzen und algorithmischen Paradigmen als praktisch relevantes Wissen zu vermitteln.

Einige Kapitelüberschriften und Stichwörter sind:

• Matching Probleme in nicht bipartiten Graphen: gewichtetes Matching, b-Matching, T-joins, Edmonds Matching Algorithmus, geometrische Dualität und der Algorithmus von Goemans und Williamson.
• Grundzüge der Polyeder Kombinatorik, total dual integrality.
• Das Rundreiseproblem: untere Schranken, Heuristiken, Approximationsalgorithmen (PTAS/FPTAS) das Euklidische TSP, das TSP Polytop, Branch and Bound Verfahren
• Covering und Packing Probleme: Heuristiken und Approximationsalgorithmen
• Quadratische Zuordnungsprobleme: untere Schranken, Heuristiken
• Matroide Dualität, Schnitt von Matroiden, Gewichteter Schnitt von Matroiden, Greedoide

• W. Cook, W. Cunningham, W. Pulleyblank und A. Schrijver, Combinatorial Optimization, Wiley, 1998.
• G. Cornuejols, Combinatorial Optimization: Packing and covering, SIAM, 2001.
• D. Hochbaum (Hrsg.), Approximation Algorithms for NP-hard problems, PWS Publishing Company, 1997.
• B. Korte und J. Vygen, Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2008.
• E. Lawler (Hrsg.), The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, 1992.

Die einstündige Übung hat einen immanenten Charakter und wird anhand der Mitarbeit der Studierenden in den Übungsstunden mit Hilfe eines Punktesystems benotet.

Punkte können auf folgenden zwei Arten erworben werden:

• Vorführung von Beispielen an der Tafel.
  Hierbei wird die Anzahl der Tafelmeldungen sowie die Qualität der Präsentation bewertet.
  Pro Tafelmeldung kann maximal 1 Punkt erworben werden.
• Spontane Ergänzungen, Kommentare, Hinweise oder Anregungen zu den an der Tafel besprochenen Beispielen und deren Lösungsweg.
  Hierbei wird ein Bonuspunkt pro bonuspunktwürdige Meldung vergeben.

Es wird ein Gesamtpunkteanzahl P nach folgendem Schema ermittelt:

P=0.5*t*(s/u)+0.5*(p/t)+0.02*B

wobei

Notenschlüssel für die Bewertung der Übung: