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

• Antragsteller: Professor Dr. Matthias Müller-Hannemann
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2003 bis 2006
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1126: Algorithmik großer und komplexer Netzwerke
• Beteiligte Person: Professor Dr. Karsten Weihe