Mathematik, Arbeitsrichtung Diskrete Optimierung
Mathematik, Arbeitsrichtung Diskrete Optimierung

Diskrete Optimierung (ADM II)

Sommersemester 2021
Dozent Max Klimm, Übungsleiter Martin Knaack
Weitere Informationen und Material auf der ISIS-Seite der Vorlesung

Inhalte
Die Vorlesung baut auf der Veranstaltung "Einführung in die kombinatorische und lineare Optimierung (ADM I)" auf. Es werden fortgeschrittene Verfahren der kombinatorischen und ganzzahligen Optimierung besprochen und analysiert, beispielsweise

  • Berechnung maximaler Branchings
  • Berechnung maximaler Matchings in allgemeinen Graphen
  • Berechnung gewichtsmaximaler Matchings in allgemeinen Graphen
  • T-Joins und das Postboten-Problem
  • Matroide und Optimierung über Matroiden
  • Komplexitätstheorie und NP-Vollständigkeit
  • Ganzzahlige lineare Programmierung
  • Problems des Handlungsreisenden

Voraussetzungen
Für die Veranstaltung ist die Kenntnis einer Programmiersprache (z.B. Python) wünschenswert. Ebenso hilfreich sich Kenntnisse in Analysis, linearer Algebra, sowie der erfolgreiche Abschluss der Veranstaltung "Einführung in die lineare und kombinatorische Optimierung (ADM I)"