 |
Universität Augsburg
|
|
|
Universität Augsburg
|
|
Jun.-Prof. Dr. Clemens Thielen
Universität Kaiserslautern
spricht am
Dienstag, 21. Juni 2016
um
16:00 Uhr
im
Raum 2004 (L1)
über das Thema:
| Abstract: |
|
Bikriterielle Optimierungsprobleme beschäftigen sich mit der gleichzeitigen Optimierung von zwei oft gegensätzlichen Zielfunktionen (z.B. Kosten und Nutzen einer Lösung). Das Ziel der Optimierung besteht hier meist darin, sogenannte Pareto-Lösungen zu bestimmen. Dies sind zulässige Lösungen des Optimierungsproblems, für die keine andere zulässige Lösung existiert, die einen der beiden Zielfunktionswerte verbessert, ohne gleichzeitig den anderen Zielfunktionswert zu verschlechtern. Jede Pareto-Lösung repräsentiert somit einen anderen Kompromiss zwischen der Optimierung der beiden Zielfunktionen und ist potentiell für einen Entscheidungsträger relevant. Die Menge aller Pareto-Lösungen wird als Pareto-Kurve bezeichnet. Alternativ zur Berechnung von Pareto-Lösungen wird häufig das einem bikriteriellen Optimierungsproblem zugeordnete budgetierte Problem betrachtet. Hier wird eine der beiden Zielfunktionen unter gleichzeitiger Berücksichtigung einer Schranke (Budgetbedingung) an die andere Zielfunktion optimiert. Unglücklicherweise existieren für die meisten bikriteriellen Optimierungsprobleme exponentiell viele verschiedene Pareto-Lösungen und das budgetierte Problem ist häufig auch dann unter komplexitätstheoretischen Gesichtspunkten schwer zu lösen, wenn das entsprechende Problem ohne Budgetbedingung effizient lösbar ist. Dies motiviert die Betrachtung von Approximationsverfahren, die in polynomineller Zeit Annäherungen an die Pareto-Kurve bestimmen oder suboptimale Lösungen des budgetierten Problems mit beweisbarer Gütegarantie liefern. Dieser Vortrag beschäftigt sich mit einem allgemein anwendbaren Approximationsverfahren für bikriterielle Minimierungsprobleme. Wir werden zeigen, wie sich für jedes bikriterielle Minimierungsproblem, bei dem die zugehörige Gewichtete-Summe-Skalarisierung in polynomineller Zeit approximiert werden kann, Approximationen sowohl für die Pareto-Kurve als auch für das budgetierte Problem effizient berechnen lassen. |
| Hierzu ergeht herzliche Einladung. |
| Prof. Dr. Tobias Harks |
Kaffee, Tee und Gebäck eine halbe Stunde vor Vortragsbeginn im Raum 2006 (L1).