Competitive Analysis for Incremental Maximization

• Applicant: Professor Dr. Yann Disser
• Subject Area: Theoretical Computer Science
• Term: from 2019 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 413095939

Incremental optimization problems arise whenever infrastructure projects need to be implemented over long periods of time, but need to be partially operational already at early stages. The purpose of this project is to establish a unified framework for incremental maximization in terms of competitive analysis. The ideal outcome is a comprehensive and reasonably fine-grained picture of the spectrum of problems that admit good incremental solutions. Seperating these problems into abstract classes of scaling difficulty, with algorithms specific to each class, allows to streamline future analysis for concrete problems. In addition, a holistic picture of incremental maximization maps out what additional assumptions need to be made in a specific application in order to improve the quality of incremental solutions. In the first part of the project, we plan to lay the formal groundwork by establishing meaningful problem classes which will be further refined throughout the project. The second and main part of the project focuses on conducting a competitive analysis for these problem classes. We will develop algorithms of varying generality, determine the competitive ratios of these algorithms, and strive to complement them with tight lower bounds. The third part of the project concentrates on studing the performance of the canonical greedy algorithm. Here we hope for necessary and sufficient conditions to reach different ranges of competitive ratios that carry over to approximation and online optimization with respect to cardinality constrained maximization problems.

• DFG Programme: Research Grants