Seminar Diskrete Optimierung

In Seminar Diskrete Optimierung sollen

  • Anwendungen, Varianten und Erweiterungen der in der Vorlesung Optimierung I besprochenen grundlegenden diskreten Verfahren
  • sowie jüngere wissenschaftliche Arbeiten zu algorithmischen und strukturellen Problemen insbesondere der Graphentheorie

vorgestellt werden.

Folgende Vorträge sind geplant:

  • 08.11.2010 Netzwerkflüsse: Einführung
  • 15.11.2010 Effiziente Algorithmen zur Bestimmung maximaler Netzwerkflüsse: Edmonds-Karp, Dinic, Karzanov
  • 6.12.2010 Spezialisierte Algorithmen zur Bestimmung maximaler Netzwerkflüsse
  • 13.12.2010 Matroide: Einführung und alternative Charakterisierungen
  • 17.01.2011 Matroide: Greedy Algorithmus
  • 31.01.2011 Submodulare Funktionen: Definition, Eigenschaften, Beispiele
  • 07.02.2011 Minimierung submodularer Funktionen

Hier die Antworten auf einige praktische Fragen.

Literatur:

R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network flows: Theory, Algorithms, and Applications, Prentice Hall.
B. Korte und J. Vygen, Combinatorial optimization, Theory and algorithms, 3rd edition, Springer.
A. Schrijver, Combinatorial Optimization, Polyhedra and efficiency, Springer.