Kompetitive Analyse für inkrementelle Maximierung

• Antragsteller: Professor Dr. Yann Disser
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 413095939

Inkrementelle Optimierungsprobleme treten immer dann auf, wenn Infrastrukturprojekte über längere Zeiträume umgesetzt werden sollen, aber währenddessen bereits eingeschränkt nutzbar sein müssen. Das Ziel dieses Projekts ist es ein Fundament für die Behandlung von inkrementellen Maximierungsproblemen mittels kompetitiver Analyse zu legen. Das Ergebnis ist idealerweise eine umfassende und verhältnismäßig feine Klassifizierung der Probleme, die gute inkrementelle Lösungen zulassen. Diese Probleme in abstrakte Klassen wachsender Schwierigkeit einzuteilen, erlaubt es die künftige Behandlung spezieller Probleme zu vereinheitlichen. Darüber hinaus zeigt ein gesamtheitliches Bild potentielle Annahmen auf, die in konkreten Anwendungen zu besseren Lösungen führen können. Im ersten Teil des Projekts wollen wir die Ergebnisse des Vorgängerprojekts zu stärken und verallgemeinern, mit dem Ziel einer vollständigen Charakterisierung der inkrementellen Lösbarkeit von kardinalitätsbeschränkten Problemen. Aufbauend auf diesen Erkenntnissen zielen wir im zweiten und zentralen Teil des Projekts darauf ab, unsere Analyse auf kapazitätsbeschränkte Probleme auszuweiten. Dies umfasst erstmals Probleme, bei denen die Kosten von Infrastrukturkomponenten von der jeweiligen Komponente und dem aktuellen Zustand der Lösung abhängen können. Wir werden Kombinationen von Ziel- und Kapazitätsfunktionen klassifizieren, die gute inkrementelle Lösungen erlauben, und wir werden Algorithmen unterschiedlicher Allgemeinheit entwickeln, ihre kompetitiven Faktoren bestimmen, und versuchen sie durch straffe untere Schranken zu ergänzen.

• DFG-Verfahren: Sachbeihilfen