Competitive Analysis for Incremental Maximization

增量最大化的竞争分析

• 批准号: 413095939
• 负责人: Professor Dr. Yann Disser
• 金额: --
• 依托单位: Arbeitsgruppe Diskrete Optimierung
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/413095939?language=en
• 关键词: Competitive; Analysis; 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.

每当基础设施项目需要长时间实施，但需要在早期阶段就已经部分运行时，就会出现增量优化问题。本研究的目的是建立一个统一的竞争分析框架，用于增量最大化。理想的结果是一个全面的和合理的细粒度的问题谱，承认良好的增量解决方案的图片。将这些问题分离成具有缩放难度的抽象类，并使用特定于每个类的算法，可以简化未来对具体问题的分析。此外，增量最大化的整体图景映射出在特定应用中需要做出哪些额外的假设，以提高增量解决方案的质量。在项目的第一部分，我们计划通过建立有意义的问题类来奠定正式的基础，这些问题类将在整个项目中进一步细化。该项目的第二部分和主要部分侧重于对这些问题类进行竞争分析。我们将开发不同的一般性算法，确定这些算法的竞争比，并努力补充他们与紧下限。第三部分主要研究规范贪婪算法的性能。在这里，我们希望的必要条件和充分条件，以达到不同范围的竞争比进行近似和在线优化基数约束的最大化问题。