Am 29. Juni 2015 referiert Prof. Dr. Helmut Alt, Professor an der Freien Universität Berlin, zum Thema "Approximationsalgorithmen zum optimalen Packen von Gegenständen". Der Vortrag beginnt um 14 Uhr in Hörsaal 5 und richtet sich insbesondere an alle Studierenden und Lehrenden der IT-Studiengänge und weitere Interessierte an Optimierungsproblemen.
Zum Vortrag:
Effizientes Packen geometrischer Objekte ist eine Fragestellung mit zahlreichen Anwendungen wie beispielsweise im Transportwesen, der Textilindustrie oder der Metallverarbeitung. Das Packen regulärer Objekte wie Kreisscheiben, höherdimensionaler Kugeln oder achsenparalleler Rechtecke ist Gegenstand intensiver Forschung in der reinen Mathematik und im Operations Research. Da sogar die einfachsten Varianten dieses Problems NP-schwer, also vermutlich nicht effizient lösbar sind, gibt man sich mit effizienten Algorithmen zufrieden, deren Lösung zwar nicht unbedingt optimal ist, sich aber höchstens um einen konstanten Faktor vom Optimum unterscheidet.
In diesem Vortrag werden weniger reguläre Objekte betrachtet sondern beliebige konvexe Polygone in der Ebene. Es wird das Problem untersucht, einen Behälter minimaler Größe zu finden, in den eine gegebene Polygonmenge gepackt werden kann, wobei man diese Polygone verschieben, aber nicht drehen darf. Insbesondere werden achsenparallele Rechtecke oder beliebige konvexe Mengen als Behälter betrachtet. Für beide Optimierungsprobleme werden Approximationsalgorithmen entwickelt.
Es handelt sich bei diesem Vortrag um neuere und allgemeinere Ergebnisse zu der Problematik, die der Referent im letzten Jahr an der FH Wedel vorstellte. Der Referent geht nach einer allgemeinen Einführung in das Thema auf seine jüngsten Forschungsergebnisse ein, die er zusammen mit Mark de Berg und Christian Knauer erzielte.
Zum Referenten:
Der Referent Prof. Dr. Helmut Alt hat die Forschungsgruppe Theoretische Informatik an der FU Berlin aufgebaut. Sie unterhält inzwischen ein dichtes Netzwerk mit Wissenschaftlern weltweit für einen regen personellen Austausch und eine akademische Zusammenarbeit. Die algorithmische Geometrie ist ein Forschungsschwerpunkt dieser Gruppe. Sie bietet exzellente Möglichkeiten für eine Promotion im Anschluss an ein Master-Studium. Prof. Sebastian Iwanowski hält engen Kontakt zu den Wissenschaftlern der Gruppe, da er selbst in dieser Forschungsgruppe promoviert hat.
In Kürze:
Was: Kolloquium: Approximationsalgorithmen zum optimalen Packen von Gegenständen
Wann: 29. Juni, 14:00 Uhr
Wo: Hörsaal 5