Competitive Analysis for Incremental Maximization

每当基础设施项目需要在很长一段时间内实施，但需要在早期阶段部分投入使用时，就会出现增量优化问题。本项目的目的是在竞争分析方面建立一个增量最大化的统一框架。理想的结果是能够提供良好的增量解决方案的一系列问题的全面和合理的细粒度图景。将这些问题分成具有可伸缩性的抽象类，并针对每一类使用特定的算法，可以简化对具体问题的未来分析。此外，增量最大化的整体图示出了为了提高增量解决方案的质量，需要在特定应用程序中进行哪些附加假设。在项目的第一部分，我们计划通过建立有意义的问题类来奠定正式的基础，这些问题类将在整个项目中进一步细化。该项目的第二部分也是主要部分集中于对这些问题类别进行竞争性分析。我们将开发各种通用性的算法，确定这些算法的竞争比，并努力用紧凑的下界来补充它们。项目的第三部分集中于研究规范贪婪算法的性能。在这里，我们希望得到关于基数约束最大化问题达到不同竞争比范围的充要条件，这些竞争比延续到逼近和在线优化。

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.