Strukturaussagen und deren Anwendung in Scheduling- und Packungsprobleme

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

Der Hauptfokus dieses Projektes ist die Entwicklung von Strukturaussagen für ganzzahlige lineare Programme (engl. integer linear Programms; kurz ILPs). Dabei möchten wir Aussagen über die genaue Form von optimalen Lösungen der ILPs treffen, beispielsweise wieviele Nicht-Null Komponenten die Lösungen besitzen oder wieviel Gewicht auf den entsprechenden Komponenten der Lösung liegt. Ein Wissen über diese Struktur hilft das entsprechenden ILP effizienter zu lösen.Wir betrachten dabei hauptsächlich ILPs, welche sich aus konkreten algorithmischen Problemstellungen wie beispielsweise dem Bin Packing Problem ergeben. In dem vorliegenden Projektantrag legen wir dar, welche Strukturbetrachtungen von Interesse sind um offene algorithmische Problemstellungen zu lösen. Wir hoffen so beispielsweise einen FPT-Algorithmus für das Bin Packing Problem mit Laufzeit 2^2^O(d) |I|^O(1), wobei |I| die Kodierungslänge der Instanz I ist, zu finden, welcher parametrisiert nach der Anzahl d der unterschiedlichen Itemgrößen ist. Dies würde das Resultat von Goemans und Rothvoß verbessern, welche bewiesen haben, dass ein Polynomialzeit-Algorithmus mit Laufzeit |I|^2^O(d) für das Bin Packing Problem existiert, wenn die Anzahl der unterschiedlichen Itemgrößen konstant ist. Außerdem möchten wir untersuchen, inwieweit sich bessere Strukturaussagen beweisen lassen, wenn lediglich approximative Lösungen gefordert sind. Die algorithmischen Implikationen wären unter anderem ein Algorithmus für das Bin Packing Problem mit Laufzeit 2^d |I|^O(1) und Güte OPT+1, sowie ein Algorithmus für das Scheduling Problem auf identischen Maschinen mit Laufzeit 2^d |I|^O(1) und Güte (1+ epsilon) OPT. Hierbei sei OPT der Wert einer optimalen Lösung. Weiterhin möchten wir als langfristiges Ziel des Projektes mit Hilfe von Strukturanalysen die sogenannte Modified Integer Roundup Property (kurz: MRP) für das Bin Packing Problem beweisen oder widerlegen. Die MRP ist eine berühmte Vermutung und sagt aus, dass der Zielfunktionswert des ILPs höchstens dem aufgerundeten Wert des relaxierten LPs plus 1 entspricht.Generell besitzen Strukturaussagen eine große Ausdrucksstärke. Sie lassen sich nicht nur auf Bin Packing anwenden, sondern auf eine Vielzahl von algorithmischen Problemen. Wir glauben daher, dass diese Techniken zu einem wichtigen Werkzeug der Algorithmik werden können.

• DFG-Verfahren: Sachbeihilfen