Prof. Dr. Martin Skutella
Die Diskrete Optimierung ist eines der jüngsten und gleichzeitig aktivsten Teilgebiete der Diskreten Mathematik. Mit der Konstruktion der ersten Computer vor mehr als 60 Jahren hat sich die Diskrete Optimierung zu einer eigenständigen mathematischen Teildisziplin entwickelt. Der Versuch, diskrete Optimierungsprobleme danach zu klassifizieren, wie effizient sie mit Computerhilfe gelöst werden können, hat die Diskrete Optimierung zum Wegbereiter wesentlicher Entwicklungen in der Theoretischen Informatik und insbesondere der Komplexitätstheorie gemacht. Heute wissen wir, dass viele interessante Probleme aus dem Bereich der Diskreten Optimierung schwer sind. Das bedeutet, dass sie unter gewissen, als sehr wahrscheinlich geltenden Annahmen aus der Komplexitätstheorie nicht effizient gelöst werden können. In diesem Vortrag erläutern wir, warum manche Probleme in der Diskreten Optimierung schwerer zu lösen sind als andere. Darüber hinaus diskutieren wir verschiedene populäre Ansätze zur algorithmischen Lösung schwerer Optimierungsprobleme.
Datum: 08.11.2012, Raum: G03-106, Zeit: 17:00