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

Es ist eine gängige Erfahrung, ass problem aus der Praxis, die in der Komplexitätstheorie als schwer (zum Beispiel NP-schwer) klassifiziert werden, dennoch of verblaiend einfach efficient lösbar sind。作为轻量级的数据，dass die Daten aus der practice typischerwise spezifische Eigenschaften haben（“现实世界的数据和最坏情况的数据”）。In den letzten Jahren ist unter dem Stichwort "parametrisierte Komplexität" In neuer, verversprechender Denkansatz entwickelt worden。引用本文：dedeer Denkansatz ist inzwischen komplexitätstheoretisch fundiert worden， and r viele klassische np - schare problem konter einige naheliegende Parametrisierungen der parametrisierte Komplexitätsstatus bestestimationwerden。在diesem project soll der umgekehrte中，praktisch相关的Weg将其写成werden: Gegeben: ein konkretes Anwendungsszenario， find: gegeignete Parameter and einen entprechenden effizenten算法。Konkrete Fragestellungen aus mehreren Anwendungsfällen auf großen Netzwerken（运输，调度，CAD，飞行，VLSI，…），in denen die Arbeitsgruppe praktische Erfahrungen gesammelt hat, sollen die Basis bilden fereine allgemeinere, systematischere analysis and ategorisierung。在这个问题上，我们的问题是如何解决的？

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.