Approximative Methoden in der Ganzzahligen Programmierung

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

Das Hauptziel dieses Antrages ist es, neue universelle Methoden zu entwickeln, um ganzzahlige lineare Programme (kurz: ILPs vom englischen "integer linear program") approximativ zu lösen. Motiviert durch aktuelle Entwicklungen in der ganzzahligen Programmierung, ist unser Ansatz, schrittweise eine zulässige Lösung des ILPs zu verbessern, indem Elemente einer bestimmten Struktur aufaddiert werden.Wir konzentrieren uns auf spezielle Klassen von ILPs, welche aus der Formulierung von konkreten algorithmischen Problemstellungen kommen, wie dem Bin Packing-Problem oder dem Scheduling-Problem auf heterogenen Maschinen. Für diese Problemstellungen gibt es bedeutende offene Fragen bezüglich ihrer Approximierbarkeit und unser Ziel ist es, bei diesen Fragen mit unserer neuen Herangehensweise Fortschritte zu erzielen.Ein weiteres Ziel des Antrages ist es, neue Algorithmen und Analysemethoden für Online Algorithmen zu entwickeln. Auch hierbei wollen wir uns Methoden und Anschauungen bedienen, welche aus der linearen und ganzzahligen Programmierung kommen. Wir betrachten ein ILP, dessen Vektor der rechten Seite sich über die Zeit ändert. Dieses Online ILP verallgemeinert diverse bekannte Online Probleme, wie zum Beispiel das klassische Online Bin Packing-Problem. Unser Ansatz zum Lösen dieses Online ILPs legt eine mächtige geometrische Interpretation des Problems nahe. Wir hoffen schließlich Online Algorithmen zu entwickeln mit einer verbesserten (asymptotischen) kompetitiven Rate für die entsprechenden Online Probleme.

• DFG-Verfahren: Sachbeihilfen