Investigating models, applications, and limitations of online algorithms

点击翻译按钮获取中文摘要

Online computation is the study of algorithm which make irrevocable decisions under incomplete or partial information. Online algorithms have numerous applications, ranging from memory management, to data compression, to resource management in cloud. There has been considerable efforts to theoretically analyze online algorithms. However, these studies often fail in introducing algorithms with practical impacts. It is because the existing works focus on improving algorithms under abstractions and using analysis measures that are not always a good reflection of practical scenarios. The ultimate objective of my research program is to model and predict the desired characteristics of a "good" online algorithm in practice. To pursue this goal, My HQP and I will consider three specific directions. The first direction concerns studying online algorithms under realistic models tailored for particular applications. We design and study algorithms for abstractions which capture the essence of applications while including details that have impacts on the performance. The second direction concerns relaxing online constraints as far as an application allows: sometimes it is possible to receive some bits of "advice" about the input and sometime an algorithm can "defer" some of its previous decisions. We design practical, "semi-online" algorithms that are augmented by limited advice or deferral power. The third direction is to study online algorithms using analysis techniques which capture both worst-case and average-case behaviour of online algorithms. We consider recently proposed measures such as Bijective analysis to study problems for which the traditional worst-case measure fails to capture typical performance of online algorithms in practice.The outcome and impact of my research program will be significant. First, it will advance the theoretical approach for analysis of online algorithms. My HQP and I will continue to publish top-rated conference and journal papers. Second, we will design practical algorithms for real-world applications such as data compression, social network partitioning, multi-core caching, and applications related to the growing field of cloud computing. The aim is not only to design good algorithms for these applications, but in doing so to create new tools and methods for analyzing a wide class of online problems. This relates to the long-term goal of my program: to combine analytical and computational techniques to characterize practical online algorithms and an array of theoretical tools for designing such algorithms. Finally, this program will directly result in the training of 2 PhD, 6 Master's, and 7 Undergraduate students. These students will develop key skills in the field of online computation, enabling them to continue research on this field and transform their knowledge to industries that use online algorithms in their products and services.