NW /2: Effiziente Vorverarbeitung für schwere Probleme: neue Techniken und pr?zise Modelle für Datenreduktion

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 hinweg kaum theoretisch analysiert. Ein Grund war, dass sich kein robustes theoretisches Modell für Vorverarbeitung finden lie?: 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 Vorverarbeitung 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 Vorverarbeitung 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.