Algorithm Engineering für NP-schwere Probleme: Parametrisierte Algorithmen versus etablierte Techniken

• Antragsteller: Dr. Falk Hüffner
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 230839996

Zahlreiche kombinatorische Probleme aus diversen Anwendungsbereichen wie Biologie, Operations Research oder Data Mining sind NP-schwer. In der Praxis werden für solche Probleme hauptsächlich Heuristiken oder Mathematisches Programmieren (ILPs) eingesetzt; diese haben jedoch meist entweder keine Garantie für ihre Lösungsqualität oder keine Garantie für ihre Laufzeit. Parametrisierte Algorithmen sind ein jüngerer Ansatz, der versucht, Probleme aus der Praxis in beweisbar kurzer Zeit optimal zu lösen. Trotz vieler Fortschritte in der Theorie und des expliziten Anspruchs der Anwendbarkeit gibt es jedoch nur wenige Arbeiten zu Implementationen und Experimenten mit "Real-World"-Daten, die zu praktisch einsatzfähiger Software führten. In diesem Projekt sollen zunächst auf der Basis der parametrisierten Algorithmik neue Verfahren zur Lösung NP-schwerer Probleme entwickelt werden; diese sollen dann implementiert und mit den herkömmlichen Ansätzen verglichen werden, um so zu allgemeineren Empfehlungen zu kommen. Weiterhin sollen parametrisierte Techniken eingesetzt werden, um Heuristiken und ILP-Ansätze zu verbessern. Auf diese Weise soll überprüft werden, inwieweit parametrisierte Algorithmik den Anspruch einlösen kann, in der Praxis relevante Lösungsverfahren zu liefern. Dazu sollen auch allgemeinere Prinzipien und Handlungsanweisungen erarbeitet werden, die zeigen, wie ein schweres Problem mit den Methoden der parametrisierten Algorithmik angegangen werden kann.

• DFG-Verfahren: Sachbeihilfen