Matroide und submodulare Funktionen

Matroide gehören zu den strukturell und algorithmisch interessantesten Mengensystemen und spielen eine zentrale Rolle in der kombinatorischen Optimierung. Sie bilden eine abstrakte Verallgemeinerung der linearen Unabhängigkeit und liefern den formalen Rahmen zum Verständnis von Greedyalgorithmen. Effiziente Algorithmen für Matroidprobleme erlauben die ebenfalls effiziente Lösung einer Reihe von scheinbar unabhängigen kombinatorischen Optimierungsproblemen. Das zweite Thema dieser Vorlesung bilden die submodularen Funktionen. Spezielle Beispiele solcher Funktionen sind die Rangfunktionen von Matroiden oder Schnittfunktionen von Graphen.

Hier einige Stichworte zum Inhalt

  • Matroide (Einführung, Definition, Beispiele)
  • Alternative axiomatische Charakterisierungen
  • Greedyalgorithmen
  • Matroid intersection
  • Matroid union
  • Submodulare Funktionen (Einführung, Definition, Beispiele)
  • Minimierung submodularer Funktionen

Die Vorlesung richtet sich an Masterstudenten unserer mathematischen Studiengängen. Sie bildet eine sinnvolle Ergänzung der "Optimierung I" sowie der "Graphentheorie", weil etliche der dort verwendeten Argumente in allgemeinerer Form behandelt werden. Die Vorlesung kann aber unabhängig von den genannten Vorlesungen gehört werden.

Dozenten: Prof. Rautenbach und Dr. Löwenstein
Vorlesung: Montags um 14:00-15:30 im He 18 E 60 (Beginn 21.10.2013)
Übung: Dienstags um 16:00-17:30 im He 22 E 19

Blatt 1

Blatt 2

Blatt 3

Blatt 4

Blatt 5


Prüfung: Mündliche Prüfung
Vorleistung: Aktive Teilnahme an den Übungen
Literatur:

  • B. Korte und J. Vygen, Kombinatorische Optimierung, Springer Verlag 2012
  • A. Schrijver, Combinatorial Optimization, Volume B, Springer Verlag 2003
  • D.B. West, Introduction to Graph Theory, Prentice Hall 2001
  • J. Oxley, Matroid Theory, Oxford Mathematics 2011

Aktuelles