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

• Applicant: Professor Dr. Matthias Müller-Hannemann
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5415670

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.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1126: Algorithmics of Large and Complex Networks
• Participating Person: Professor Dr. Karsten Weihe