Datenreduktion in der parametrisierten Algorithmik: neue Modelle und Methoden (DAMM)

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 218550609

Ziel des Projektes DAMM ( Datenreduktion in der parametrisierten Algorithmik: neue Modelle und Methoden) ist die Entwicklung beweisbar effizienter und effektiver Datenreduktionsregeln (im Sinne des Problemkernkonzepts) fur NP-schwere Berechnungsprobleme. Dazu sollen sowohl neue Problemkernkonzepte (beispielsweise sogenannte Turing-Kerne oder partielle Kerne) auf ihre Anwendbarkeit hin untersucht und bewertet werden als auch klassische Techniken der Kernelisierung bezogen auf (multivariate) Nichtstandardparameter analysiert werden (hier verschob sich unser Fokus insbesondere auf neue Anwendungsfelder wie Maschinelles Lernen, Data Mining und angrenzende Themen). In besonders erfolgversprechenden Fallen soll eine empirische Validierung der gewonnen Verfahren nachfolgen. Im Vergleich zum Vorantrag gibt es keine grundsätzlichen Themenänderungen, es gibt aber eine stärkere Schwerpunktsetzung in Richtung Problemfelder wie Maschinelles Lernen und Datenclustering. Darüber hinaus rückt noch stärker ins Zentrum das Anliegen, bestehende heuristische Lösungsansätze hingehend auf ihre versteckten Datenreduktionsqualitäten zu analysieren, zu verstehen und eventuell zu verbessern. Weiterhin eine zentrale Bedeutung im Projekt haben nichtklassische Problemkernkonzepte wie multivariate Kerne, partielle Kerne, schwache Kerne und natürlich Turing-Kerne und ihre Derivate wie Truth-Table-Kerne. Unsere bisher gewonnenen Einsichten deuten klar auf die Notwendigkeit und auch Fruchtbarkeit derartiger Relaxierungen des Problemkernkonzepts hin. Weiterhin wird in der zweiten Projektphase anvisiert, neu entwickelte Datenreduktionsalgorithmen zu implementieren und ihre Qualitäten so auch empirisch zu überprüfen.

• DFG-Verfahren: Sachbeihilfen