Approximative Methoden in der Ganzzahligen Programmierung

• Antragsteller: Professor Dr.-Ing. Kim-Manuel Klein
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 445520385

Das Hauptziel dieses Projektes ist es basierend auf einem strukturellen Verständnis, neue Techniken zur Entwicklung von approximativen Algorithmen für Packungs- und Scheduling-Probleme zu erforschen. Anstatt wie bisher die Eingabeinstanzen zu runden sollen die ILP Algorithmen angepasst werden um mit den originalen (nicht gerundeten) Itemgrößen zu operieren. Damit dies funktionieren kann, benötigen wir fundamentale mathematische Strukturaussagen über die Form und Existenz von approximativen Lösungen. Mit Hilfe dieser neuen Methoden möchten wir hauptsächlich zwei Dinge erreichen: Zum einen möchten wir sogenannte additive Approximationsschemata für fundamentale Packungs- und Scheduling-Probleme entwickeln, wie zum Beispiel für das Rucksackproblem und für das Makespan-Scheduling-Problem. Ein additives Approximationsschemata hat dabei eine Gütegarantie der Form OPT + \epsilon a , wobei a ein problemspezifischer Parameter ist - beispielsweise die maximale Itemgröße. Da typischerweise a << OPT gilt, hat diese Gütegarantie Vorteile gegenüber den klassischen Approximationsschemata mit einer Gütegarantie von (1+ \epsilon)OPT. Im Rahmen dieses Projektes möchten wir grundlegende Techniken und Einsichten finden um approximative Algorithmen dieser Form zu entwickeln. Es ergeben sich interessante Zusammenhänge zum Bereich der parametrisierten Komplexität für Scheduling- und Packungsprobleme. Als ein weiteres Ziel dieses Projektes möchten wir mit Hilfe dieses neuen Ansatzes bekannte offenen Fragen im Bereich des Flow-Time-Schedulings beantworten.

• DFG-Verfahren: Sachbeihilfen