BSF: 2014414: New Challenges and Perspectives in Online Algorithms

虽然传统的算法设计和分析假设算法可以获得整个输入的完整知识，但在线算法领域处理的是输入是以部分显示的情况，并且在线算法被要求在到达后立即对每个新部分做出响应，而不知道未来。在线算法之前的决定不能被撤销。因此，在线计算的主要问题是在不确定的情况下获得良好的性能，因为算法的未来是未知的。这种情况下的问题出现在所有计算机科学中，也出现在许多序列决策、机器学习和许多其他领域。所提出的研究集中在对在线算法设计的原始-对偶方法的更深入的研究上。该项目研究的主题是(A)将线性优化的成功推广到凸情形，(B)放松变量的单调性，为具有抢占性的算法开发原则性方法，以及(C)理解在线原始-对偶方法和在线机器学习算法之间的联系。作为更广泛影响的一部分，这项研究可能会为传统算法设计以及机器学习和算法博弈论等其他领域的各种问题带来更好的算法。

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.