BSF: 2014414: New Challenges and Perspectives in Online Algorithms

BSF：2014414：在线算法的新挑战和前景

• 批准号: 1540541
• 负责人: Anupam Gupta
• 金额: $ 4万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1540541&HistoricalAwards=false
• 关键词: BSF; 2014414; New; Challenges; Perspectives

While the traditional design and analysis of algorithms assumes that complete knowledge of the entire input is available to the algorithm, the area of online algorithms deals with the case where the input is revealed in parts, and the online algorithm is required to respond to each new part immediately upon arrival, without knowledge of the future. Previous decisions of the online algorithm cannot be revoked. Thus, the main issue in online computation is obtaining good performance in the face of uncertainty, since the future is unknown to the algorithm. The problems in this setting arise in all of computer science, as well in much of sequential decision-making, machine learning, and many other areas.The proposed research is focused on a deeper investigation of the primal-dual approach to online algorithm design. The topics investigated in this project are (a) extending the success of linear optimization to the convex case, (b) relaxing monotonicity of the variables and developing principled approaches for algorithms with preemption, and (c) understanding the connection of online primal-dual approaches and online machine learning algorithms. As part of the broader impact, the research is likely to lead to better algorithms for a variety of problems both in traditional algorithm design and in other areas like machine learning and algorithmic game theory.

虽然传统的算法设计和分析假设算法可以获得整个输入的完整知识，但在线算法领域处理输入部分公开的情况，并且在线算法需要响应每个新的输入。到达后立即分开，不知道未来。在线算法之前的决定无法撤销。因此，在线计算的主要问题是在面对不确定性时获得良好的性能，因为算法未知未来。这种情况下的问题出现在所有计算机科学以及顺序决策、机器学习和许多其他领域中。拟议的研究重点是对在线算法设计的原对偶方法进行更深入的研究。该项目研究的主题是（a）将线性优化的成功扩展到凸情况，（b）放松变量的单调性并开发抢占算法的原理方法，以及（c）理解在线原对偶的联系方法和在线机器学习算法。作为更广泛影响的一部分，这项研究可能会为传统算法设计以及机器学习和算法博弈论等其他领域的各种问题带来更好的算法。