Kompetitive Analyse für inkrementelle Maximierung

• Antragsteller: Professor Dr. Yann Disser
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2023
• 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 dieses Projekts wollen wir formale Grundlagen schaffen, indem wir sinnvolle Problemklassen definieren, die in Laufe des Projekts weiter verfeinert werden sollen. Der zweite und zentrale Teil des Projekts beschäftigt sich mit der kompetitiven Analyse dieser Klassen. Wir werden Algorithmen unterschiedlicher Allgemeinheit entwickeln, ihre kompetitiven Faktoren bestimmen, und versuchen sie durch straffe untere Schranken zu ergänzen. Im dritten Teil des Projekts konzentrieren wir uns darauf notwendige und hinreichende Bedingungen für die Lösungsgüte des kanonischen Greedy-Algorithmus zu untersuchen. Diese Bedingungen sollten sich auf Approximationsgarantieen und die Online-Optimierung für die zugrunde liegenden kardinalitätsbeschränkten Optimierungsprobleme übertragen lassen.

• DFG-Verfahren: Sachbeihilfen