Algorithm Engineering für Skalierbare Datenreduktion

• Antragsteller: Professor Dr. Christian Schulz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 471903337

Viele wichtige Optimierungsproblems unserer Welt sind NP-hart: es wird erwartet das kein effizienter (polynomialzeit) Algorithmus existiert der immer eine optimale Lösung für die Problem findet. Allerdings hat sich gezeigt das viele NP-harte Probleme fixed-parameter tractable (FPT) sind: große Eingaben können effizient und nachweisbar optimal gelöst werden so lange ein bestimmter Problemparameter klein ist. In den letzten zwei Jahrzehnten wurden für eine große Menge von Problemen signifikante Fortschritte im Design und der Analyse solcher FPT Algorithmen gemacht. Dies beinhaltet Techniken die die Eingabe eines Problems in Teile zerlegt, um es dann mit einem "Teile-und-herrsche" Ansatz zu lösen, oder Techniken die die Problemgröße reduzieren können ohne die Lösung des Problems zu verändern. Allerdings wurden diese theoretische Ideen bisher nur wenig in der Praxis untersucht -- nur wenige FPT-Algorithmen wurden implementiert und auf realen Datensätzen getestet. Das praktisches Potenzial dieser Algorithmen ist noch lange nicht verstanden. Durch nicht-triviale Anwendung von Techniken aus dem FPT Bereich können Algorithmen erhalten werden, die sich hervorragend für reale Probleme und Eingaben eignen.Dieses Projekt zielt darauf ab die Lücke zwischen Theorie und Praxis die derzeit in diesem Bereich beobachted wird für eine Auswahl an wichtigen Problemen in der Praxis zu überbrücken -- insbesondere im Kontext von Anwendungen die mit großen Datenmengen umgehen, wie z.B. Minimum Fill-In Problem, das häufig in großen physikalischen Simulationen verwendet wird oder z.B. das gewichtete Independent Set Problem das wichtige Anwendung in Maplabelling oder in Logistik bei Großkonzernen hat. Zu jedem Zeitpunkt im Projekt werden wir die Algorithmen soweit wie möglich skalieren, z.B. durch geeignete Parallelisierungen. Dies wird zu Algorithmen führen, die robuster und flexibler sind, bessere Lösungen erzeugen und auf massiv parallelen Maschinen und Instanzen skalieren, die viel größer als bisher möglich sind. Darüber hinaus zielt das Projekt darauf ab, mit Forschern aus verschiedenen Anwendungsbereichen zusammenzuarbeiten, um die entwickelten technischen Verfahren direkt in die Praxis umzusetzen. Das Ziel des Projekts ist daher ein umfassender Ansatz der Algorithm Engineering Forschung, der sowohl exzellente Algorithmenforschung als auch die Lösung konkreter Anwendungen beinhaltet.

• DFG-Verfahren: Sachbeihilfen