Effiziente Vorverarbeitung für schwere Probleme: neue Techniken und präzise Modelle für Datenreduktion

• Antragsteller: Professor Dr. Stefan Kratsch
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 225019562

Vorverarbeitung, im Sinne von Datenreduktion, ist von fundamentaler Bedeutung für die praktische Lösung NP-schwerer Probleme. Ein sehr erfolgreiches Beispiel ist das kommerzielle Tool CPLEX zur Lösung ganzzahliger linearer Programme, bekannt für seine starke Vorverarbeitung. Trotzdem wurde Vorverarbeitung über lange Zeit kaum theoretisch analysiert. Ein Grund war, dass sich kein robustes theoretisches Modell für Vorverarbeitung finden liess: Eine Routine die jede Instanz in Polynomialzeit verkleinert, könnte das gesamte Problem in Polynomialzeit lösen (unmöglich wenn nicht P = NP). Der Begriff der Kernelisierung aus dem jungen Gebiet der parametrisierten Komplexität umgeht dieses Problem: Eine Kernelisierung generiert eine äquivalente Instanz deren Größe durch eine Funktion eines Parameters der Eingabe beschränkt ist; die Größe der Eingabe spielt keine Rolle. Polynomielle Kernelisierungen, also mit Outputgröße polynomiell im Parameter, haben sich zu einem dynamischen Forschungsgebiet entwickelt. Ziel dieses Projekts ist eine grundlegende Vertiefung des Wissens über Vorverarbeitung, ausgehend vom Begriff der Kernelisierung. Dafür sollen einerseits neue Techniken für Kernelisierungen und untere Schranken entwickelt werden. Andererseits sollen aber auch andere Modellierungen für effiziente Vorverarbeitung untersucht werden. Gerade das Zusammenspiel dieser beiden Ziele soll zu möglichst präzisen Erkenntnissen über Vorverabeitung führen. Eine Motivation sind aktuelle Techniken zu unteren Schranken. Unter komplexitätstheoretischen Annahmen lässt sich damit für manche Probleme die Existenz polynomieller Kernelisierungen ausschließen. Es hat sich aber herausgestellt, dass dann auch allgemeinere Modelle von Vorverarbeitung für diese Probleme ausgeschlossen sind; darunter praxisrelevante aber auch eher theoretische Varianten. Die Techniken sind also nicht gänzlich in der Lage die Frage nach der Existenz effizienter Vorverarbeitung zu beantworten. In PREMOD soll dem nachgegangen werden: Gibt es praxistaugliche Modelle die nicht ausgeschlossen sind? Können wir präzisere Techniken für untere Schranken entwickeln? Wann können wir feststellen, dass ein Problem keine effiziente Vorverabeitung erlaubt? Eine weitere Motivation ist das Interesse an der Anwendbarkeit von Kernelisierungsresultaten. PREMOD soll durch Untersuchung strengerer Modelle sowie durch Experimente dazu beitragen: Sind bestehende Kernelisierungen auch zeit- und speichereffizient umsetzbar? Lässt sich die Parameterwahl verbessern, so dass stärkere Resultate erzielt werden? Wie gut ist das Zusammenspiel mit Approximationsalgorithmen oder Heuristiken? Gibt es präzisere Modelle für die erfolgreichen, einfachen und lokalen Reduktionsregeln aus der Praxis? Zusammenfassend steht PREMOD für die Entwicklung praxisrelevanter und zugleich theoretisch robuster Modelle für Vorverarbeitung.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen