Laufzeitschranken für Scheduling- und Packungsprobleme unter Annahme der Exponentialzeithypothese

• Antragsteller: Professor Dr. Klaus Jansen
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 236400547

Wir untersuchen verschiedene Scheduling- und Packungsprobleme. Bei Schedulingproblemen sollen Jobs mit vorgegebenen Bearbeitungszeiten auf Maschinen verteilt werden. Ziel ist zumeist die möglichst schnelle Fertigstellung aller Jobs. Bei Packungsproblemen werden Gegenstände in Behälter mit beschränkter Kapazität gepackt, sodass die Kosten (beispielsweise Anzahl oder Größe der Behälter) minimiert werden. Die computergestüzte Berechnung von optimalen Lösungen solcher Probleme benötigt zu lange, um praktisch angewendet zu werden. Zwar werden und wurden immer schnellere Algorithmen entwickelt, aber oft werden nur noch kleine Verbesserungen erzielt. Wir vermuten, dass dies durch die prinzipielle Schwierigkeit der Probleme bedingt ist. Daher möchten wir die Komplexität dieser Probleme systematisch untersuchen und beweisen, dass die Laufzeit gewisse Grenzen nicht unterschreiten kann. Dies schließt die Existenz von Algorithmen mit schnellerer Laufzeit aus.Ein fundamentales Problem der Komplexitätstheorie ist 3-SAT. Es besteht darin, die Variablen einer logischen Formel mit 'wahr' und 'falsch' so zu belegen, dass die Formel 'wahr' ist. Die vorherrschende Meinung ist, dass die Laufzeit von Algorithmen für 3-SAT exponentiell in der Anzahl der Variablen und damit schon für moderate viele Variablen praktisch nicht lösbar ist. Diese Annahme wird als Exponentialzeithypothese bezeichnet. Wir wollen das Problem 3-SAT so umformen, dass es durch die verschiedenen Scheduling- oder Packungsprobleme ausgedrückt werden kann. Dadurch kann ein Algorithmus für das jeweilige Scheduling- oder Packungsproblem ebenfalls 3-SAT lösen. Dadurch überträgt sich die Mindestlaufzeit auf das Scheduling- oder Packungsproblem.Neben exakten Algorithmen, die eine optimale Lösung berechnen, verwendet man oft approximative Algorithmen, deren Lösungen in einem beschränkten Rahmen vom Optimum abweichen dürfen, aber wesentlich schneller sind. Für beide Arten von Algorithmen wollen wir Mindestlaufzeiten beweisen. Wir erhoffen uns, dass dadurch die Optimalität einiger bereits bekannter Algorithmen gezeigt werden kann. Außerdem erwarten wir, dass nicht bei allen untersuchten Problemen die gefunden Mindestlaufzeit der Laufzeit von bekannten Algorithmen entspricht. Für diese Probleme wollen wir schnellere Algorithmen entwickeln, um diese Lücke zu verkleinern und gegebenenfalls ganz zu schließen. Trotz ihrer schlechten Laufzeit sind exakte Algorithmen oft nützlich beim Entwurf von approximativen Algorithmen. Viele von diesen berechnen exakte Lösungen für einen Teil des ursprünglichen Problems. Eine Verbesserung von exakten Algorithmen hat daher unmittelbaren Einfluss auf die Qualität der durch approximative Algorithmen berechneten Lösungen.

• DFG-Verfahren: Sachbeihilfen