Fein-granulare Komplexität und Algorithmen für Scheduling und Packungen

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

Scheduling- und Packungsprobleme gehören zu den am besten erforschten Problemen der Informatik, Mathematik und des Operations Research. Tausende von Arbeiten haben sich in den letzten Jahrzehnten mit diesen Problemen beschäftigt und dabei eine Vielzahl an Algorithmen für ihre Lösung vorgestellt. Manche dieser Algorithmen lösen die Probleme exakt, andere geben eine approximative Lösung und wiederum andere funktionieren nur für Spezialfälle in Polynomialzeit. All diese Algorithmen geben uns eine obere Schranke für die Komplexität dieser diversen Packungs- und Schedulingprobleme, sei es nun im Hinblick auf die Laufzeit zum Finden einer optimalen Lösung oder im Hinblick auf die Güte einer Lösung, die in Polynomialzeit berechnet werden kann. Im Gegensatz dazu zeigt sich die Entwicklung unterer Schranken traditionell als sehr schwierig, da selbst die Annahme P ungleich NP nicht stark genug ist, um solche Schranken zu beweisen. In den letzten drei Jahrzehnten wurden daher stärkere Vermutungen über die Komplexität von NP-schweren Problemen entwickelt. Die berühmteste ist die Exponentialzeit-Hypothese (ETH), welche aussagt, dass das klassische 3-SAT Problem nicht in subexponentieller Zeit 2^{o(n)} gelöst werden kann. Unter dieser Annahme wurden viele bahnbrechende Ergebnisse bewiesen, die entweder zeigten, dass einige Algorithmen bereits optimal sind oder die Lücken aufzeigten, bei denen eine Verbesserung möglich sein könnte. In diesem Projekt möchten wir die oben genannten Techniken auf das Gebiet des Operations Research übertragen. Wir möchten ein Framework entwickeln, um die Optimalität wichtiger Algorithmen für Packungs- und Schedulingprobleme zu beweisen, sowohl für exakte Verfahren als auch für Approximationsalgorithmen. An den Stellen, wo unser Framework Möglichkeiten für algorithmische Verbesserungen liefert, möchten wir bessere Algorithmen entwickeln, die die unteren Schranken treffen. Zur Unterstützung dieser algorithmischen Verbesserungen planen wir auch, schon lange offene Probleme über die Approximierbarkeit von Scheduling- und geometrischen Packungsproblemen anzugehen.

• DFG-Verfahren: Sachbeihilfen