Kombinatorische Optimierung und Geometrie

Frau P. Huhn
Packungsprobleme

Das Rucksackproblem, bei dem man mit Gewichten und Nutzen versehene Objekte unter Einhaltung eines Maximalgewichts einpacken und den Gesamtnutzen maximieren möchte, ist ein intuitiv verständliches Optimierungsproblem. Es gehört zu einer Klasse von Packungsproblemen, die eine Vielzahl von Anwendungen in der Praxis haben, aber trotz einfacher Formulierung theoretisch nur schwer zu lösende kombinatorische Optimierungsprobleme darstellen. Wir werden einfache Heuristiken und aufwändige exakte Lösungsverfahren, ebenso wie verwandte praktische Problemstellungen vorstellen und so einen Einblick in die kombinatorische Optimierung liefern.

Herr W. Klotz
Heiraten, aber wen?

Beim Heiratsproblem stehen sich n Männer und n Frauen gegenüber, die sich nur zum Teil kennen. Die Aufgabe besteht darin, n Paare zu bilden aus Partnern, die sich gegenseitig kennen. Damit das klappt, müssen je k Männer zusammen mindestens k der gegenüberstehenden Frauen kennen. Der Heiratssatz (Philip Hall, 1935) besagt, dass diese nahe liegende Bedingung nicht nur notwendig, sondern auch hinreichend ist für die Lösung der Aufgabe. Das Heiratsproblem (Matchingproblem) hat viele Varianten, Anwendungen und algorithmische Lösungen. Darüber wird berichtet.

Herr T. Sander
Quadratur des Quadrats

Im Jahre 1903 zeigte Max Dehn, dass ein Rechteck und Quadrate (insbesondere unterschiedlicher Größe), welche das Rechteck parkettieren, kommensurable Seiten besitzen. 1925 gelang erstmalig die explizite Parkettierung eines Rechtecks mit paarweise verschiedenen Quadraten und um 1940 entstanden die ersten entsprechenden Beispiele für ein Quadrat. Der Vortrag wird Problem und Lösungsmethoden beleuchten, wobei der Einsatz von Rechnern, aber auch Netzwerke elektrischer Ströme und das Kirchhoffsche Gesetz eine Rolle spielen.

Programm