Seminar Kombinatorische Optimierung

Inhalt
In diesem Seminar behandeln wir Themen, die die Inhalte der Vorlesung Optimierung und OR 1 ergänzen und vertiefen. Das Seminar kann entweder im Bachelor oder im Master angerechnet werden. Erwartet wird ein guter Vortrag von ca. 90 Minuten auf Deutsch oder Englisch. Eine schriftliche Ausarbeitung wird nicht verlangt. Fragen zu Vortrag oder Material können Sie in der Sprechstunde klären.

Als Quelle verwenden wir hauptsächlich die folgenden zwei Bücher:

  • Cook, Cunningham, Pulleyblank, Schrijver, Combinatorial Optimization, Wiley.
  • Korte, Vygen, Combinatorial Optimization, 5th edition, Springer.
    (Von diesem Buch existieren auch deutsche Ausgaben, die Sie verwenden können.)

Zeit und Ort:  Montags 10:15-11:45 und E03 in Heho 22.

Bereits vergebene Vortragsthemen

  • 24.10 Minimum cuts in undirected graphs
  • 07.11 Gomory Hu Trees
  • 14.11 Edmonds' Branching Algorithm
  • 21.11 Spanning Tree Polytope
  • 28.11 Unimodulare Transformationen
  • 12.12 Total Dual Integrality
  • 19.12 Total Unimodularity
  • 16.01 Dinic's, Karzanov's, and Fujishige's Algorithm
  • 23.01 Goldberg-Tarjan Algorithm
  • 30.01 Minimum Mean Cycle
  • 06.02 Network Simplex Algorithm
  • 13.02 Minimum Mean Cycle Cancelling Algorithm

Mögliche weitere Vortragsthemen

  • Max-Flow-Min-Cut Anwendungen
  • Multicommodity Flows
  • Matchingalgorithmen
  • Minimum Weight Perfect Matching
  • T-Joins and Postman Problems

Aktuelles

Die Vortragstermine wurden festgelegt. Der erste Vortrag findet am 24.10. statt. Das Seminar findet im Raum E03 in der Heho 22 statt. (Der E03 ist wohl der ehemalige E19).