Home Detail

Kombinatorische Optimierung: Algorithmen und Resultate für ausgewählte Anwendungen

Lecturer: Dr. Frauke Liers (Mathematisch‐Naturwissenschaftliche Fakultät, Universität Köln)




Kombinatorische Optimierungsprobleme tauchen in vielen realistischen Problemstellungen auf. Während für einige Aufgaben, z.B. kürzeste‐Wege‐Probleme, glücklicherweise Polynomialzeitverfahren bekannt sind, erweisen sich andere Probleme, z.B. das Handlungsreisendenproblem, als NP‐schwer.

Im Vortrag werden verschiedene Optimierungsprobleme zusammen mit exakten
Lösungsverfahren und effizienten Implementierungen für realistische Anwendungen vorgestellt. Im Fokus stehen dabei insbesondere Partitionierungsprobleme in Graphen, die je nach Ausrichtung polynomiell lösbar oder NP‐schwer sein können. Anwendungen finden sich in der theoretischen Physik, aber auch beim Entwurf moderner elektronischer Schaltkreise sowie dem robusten Design von Kommunikationsnetzen.

Download:

back