Competitive Analysis for Incremental Maximization

• Applicant: Professor Dr. Yann Disser
• Subject Area: Theoretical Computer Science
• Term: since 2019
• 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 strengthen and generalize the results of the precursor project towards a full characterization of incremental solvability of cardinality-constrained problems. Based on these insights, in the second and main part of the project we aim to extend our analysis to capacity-constrained problems. Importantly, this encompasses problems where the costs of infrastructure components may depend on the component and the current state of the solution. We will classify combinations of objective and capacity functions that allow for good incremental solutions, and we will develop algorithms of varying generality, determine the competitive ratios of these algorithms, and strive to complement them with tight lower bounds.

• DFG Programme: Research Grants