Entwicklung von effizienten polynomiellen Approximationsschemata für Scheduling- und verwandte Optimierungsprobleme

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

Das Hauptziel des Forschungsvorhabens ist die Entwicklung und Analyse von effizienten polynomiellen Approximationsschemata für wichtige Scheduling- und Knapsackprobleme. Für viele schwierige Optimierungsprobleme existieren sogenannte polynomielle Approximationsschemata, mit denen man in polynomieller Zeit eine Lösung in der Nähe vom Optimum für jede Eingabe I und jede Genauigkeit ε > 0 finden kann. Ein wichtiges Beispiel ist ein Approximationsschema von Hochbaum und Shmoys [24, 25] zur Bestimmung eines approximativen Ablaufplans oder Schedules für n Jobs auf m uniformen Prozessoren mit unterschiedlichen Geschwindigkeiten. Die Laufzeit des Algorithmus ist (n/ε)σ(1/ε²). Wenn die Genauigkeit ε > 0 jedoch klein ist (z.B. ε = 1/10), dann ist die Laufzeit des Algorithmus extrem groß und für praktische Anwendungen leider unbrauchbar. Ziel des Forschungsvorhabens ist es, die Laufzeiten der bisher besten Algorithmen für das obige Schedulingproblem und verwandte Probleme zu verbessern. Die Zielrichtung ist hierbei eine Laufzeit der Approximationsschemata von etwa 2σ(1/ε) + poly(n) zu erhalten, wobei poly(n) ein kleines Polynom in der Anzahl n der Jobs ist. Dazu werden wir versuchen Algorithmen zur approximativen Lösung von linearen und ganzzahligen linearen Programmen weiter zu verbessern. Außerdem wollen wir an einigen offenen Fragen zum klassischen Bin Packing arbeiten, das als Teilproblem ebenso auftritt. Eine obige Laufzeit würde eine enorme Verbesserung bedeuten, weil die entsprechenden Algorithmen dann für praktische Anwendungen besser zu verwenden sind. Zusätzlich wollen wir untere Schranken für die Laufzeit der Algorithmen bestimmen; und zwar dass bessere Laufzeiten unter bestimmten komplexitätstheoretischen Annahmen nicht möglich sind.

• DFG-Verfahren: Sachbeihilfen