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.

虽然传统的算法设计和分析假设整个输入的完整知识可用于算法，但在线算法领域处理输入以部分形式显示的情况，并且在线算法需要在到达时立即响应每个新部分，而不知道未来。在线算法的先前决定不能被撤销。因此，在线计算中的主要问题是在面对不确定性时获得良好的性能，因为未来对算法来说是未知的。在这种情况下出现的问题在所有的计算机科学，以及在许多顺序决策，机器学习，和许多其他areages.The建议的研究集中在一个更深入的调查的原始-对偶方法在线算法设计。在这个项目中研究的主题是（a）扩展线性优化的成功凸的情况下，（B）放松单调的变量和开发原则的方法与抢占算法，和（c）了解在线原始对偶方法和在线机器学习算法的连接。作为更广泛影响的一部分，这项研究可能会为传统算法设计以及机器学习和算法博弈论等其他领域的各种问题带来更好的算法。