Evaluierung und Weiterentwicklung des parametrischen Ansatzes für algorithmische Graphenprobleme aus der Praxis

点击翻译按钮获取中文摘要

Es ist eine gängige Erfahrung, dass Probleme aus der Praxis, die in der Komplexitätstheorie als schwer (zum Beispiel NP-schwer) klassifiziert werden, dennoch oft verblüffend einfach effizient lösbar sind. Das liegt daran, dass die Daten aus der Praxis typischerweise spezifische Eigenschaften haben ("Realweltdaten sind keine Worst-Case-Daten"). In den letzten Jahren ist unter dem Stichwort "parametrisierte Komplexität" ein neuer, vielversprechender Denkansatz entwickelt worden. Dieser Denkansatz ist inzwischen komplexitätstheoretisch fundiert worden, und für viele klassische NP-schwere Probleme konnte für einige naheliegende Parametrisierungen der parametrisierte Komplexitätsstatus bestimmt werden. In diesem Projekt soll der umgekehrte, praktisch relevantere Weg beschritten werden: Gegeben: ein konkretes Anwendungsszenario, finde: geeignete Parameter und einen entsprechenden effizienten Algorithmus. Konkrete Fragestellungen aus mehreren Anwendungsfällen auf großen Netzwerken (Transport, Scheduling, CAD, Fließbandplanung, VLSI, ...), in denen die Arbeitsgruppe praktische Erfahrungen gesammelt hat, sollen die Basis bilden für eine allgemeinere, systematischere Analyse und Kategorisierung. Einen besonderen Schwerpunkt sollen dabei multikritierielle Optimierungsprobleme bilden.