Datenreduktion und Problemkerne

• Applicants: Professor Dr. Jiong Guo; Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 43721172

Ziel des Projekts DARE ist die Entwicklung von in Polynomzeit ausführbaren Datenreduktionsregeln zur Gewinnung von Problemkernen für NP-schwere, parametrisierte Probleme. Dabei versteht man unter einem Problemkern eine zur Ursprungsinstanz äquivalente Instanz, deren Größe jedoch allein durch eine Funktion des Parameters beschränkt ist. Besonders wünschenswert sind Problemkerne polynomieller oder sogar linearer Größe. Mit dem Konzept der Problemkerne besteht erstmals ein theoretisch fundierter Zugang zur Analyse der Wirksamkeit von Datenreduktionsregeln und Preprocessing, ein wichtiger Ansatz zur Lösung NP-schwerer Probleme. Die „Problemkernalgorithmik“ hat sich in wenigen Jahren zu einem herausragend wichtigen Teilgebiet der parametrisierten Algorithmik gemausert. Die Antragsteller haben hierzu einen wesentlichen Beitrag geleistet und wollen diese erfolgreiche, international sichtbare Arbeit auf möglichst breiter Basis fortführen und ausbauen. Es gilt, die Pioniertage dieses auch außerhalb der parametrisierten Algorithmik sehr heißen und immer populärer werdenden Themas mitzugestalten. Das Projekt DARE soll hierfür das Fundament bilden.

• DFG Programme: Research Grants