BSF: 2014414: New Challenges and Perspectives in Online Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.