Grenzen der Packungsprobleme — Transfer von Methoden und Algorithmen

• Antragsteller: Dr. Karol Wegrzycki
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 559177164

Packungsprobleme, die in der Informatik allgegenwärtig sind, stellen Forscher vor die Herausforderung, Objekte effizient in Behälter zu füllen, und treten in verschiedenen Bereichen wie Optimierung, algorithmischer Geometrie, Operations Research und Logik auf. Dennoch bleiben exakte Methoden und Ideen oft auf spezifische Teilgebiete der theoretischen Informatik beschränkt. In diesem Projekt zielen wir darauf ab, das Wissen und die Methodologien von Packungsproblemen zwischen diesen Feldern zu transferieren. Unser Ziel ist es, allgemein anwendbare Techniken und Berechenbarkeitsgrenzen zu identifizieren. Es werden vier zentrale Schwerpunkte behandelt. Optimierung: Verbesserung der Komplexität von Knapsack-Problemen, Algorithmische Geometrie: Adaptierung von Approximationsmethoden für geometrische Kontexte, Operations Research: Verfeinerung exakter Lösungsverfahren für Planungsprobleme, Algorithmische Logik: Untersuchung der feinkörnigen Komplexität von Problemen der Logik. Unser Plan ist es, Methoden aus den jeweiligen Bereichen zu adaptieren. Zum Beispiel planen wir, zur Lösung des Knapsack-Problems Methoden aus der Kryptographie zu verwenden. Um Algorithmen in der Geometrie oder Logik zu verbessern, beabsichtigen wir, Werkzeuge aus der Optimierung zu nutzen, um die Anzahl der Zustände in der dynamischen Programmierung besser zu beschränken. Ebenso möchten wir Erkenntnisse aus parametrisierten Algorithmen und der Graphentheorie nutzen, um Algorithmen im Operations Research für Planungsprobleme zu verbessern. Wir hoffen, dass unser Projekt durch eine rigorose Analyse die Zusammenarbeit zwischen diesen Feldern beschleunigt und ein tieferes Verständnis über die verschiedenen Bereiche der theoretischen Informatik hinweg fördert.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen