Strukturaussagen für ganzzahlige lineare Programme

• Antragsteller: Professor Dr. Klaus Jansen
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 528381760

Der Fokus dieses Projekts ist die Entwicklung von effizienten Algorithmen und Strukturaussagen für sogenannte ganzzahlige lineare Programme (eng.: ILPs). Diese sehr allgemeine Form von Optimierungsproblemen hat viele Anwendungen im Bereich der kombinatorischen Optimierung und ein effizienterer Algorithmus zum Lösen von ILPs hätte Auswirkungen in vielen Bereichen der theoretischen Informatik. Genaueres Wissen über die Struktur der Lösungen führt oft zu unmittelbaren algorithmischen Anwendungen, in denen die Eigenschaften einer Lösung zur Beschränkung oder erleichterten Suche einer Lösung genutzt werden können. Wir glauben, dass Strukturaussagen über Lösungen von ILPs als universelles Werkzeug zur Entwicklung von effizienten Algorithmen - sowohl direkt für ILPs, als auch für die vielen Anwendungen dieser - dienen können. Gleichzeitig wollen wir bekannte Algorithmen bezüglich ihrer Laufzeit verbessern oder untere Laufzeitschranken basierend auf Komplexitätsannahmen wie z.B. der Exponentialzeit-Hypothese, einer Annahme zur Laufzeit von Algorithmen zur Lösung des Erfüllbarkeitsproblems (eng.: SAT), beweisen.

• DFG-Verfahren: Sachbeihilfen