Investigating models, applications, and limitations of online algorithms

研究在线算法的模型、应用和局限性

• 批准号: RGPIN-2018-06687
• 负责人: Kamali, Shahin
• 金额: $ 0.84万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749838
• 关键词: Investigating; models; applications; limitations; online

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.

在线计算是研究在不完全或部分信息下做出不可撤销决策的算法。在线算法有许多应用，从内存管理到数据压缩，再到云中的资源管理。对在线算法的理论分析已经有了相当大的努力。然而，这些研究往往未能引入具有实际影响的算法。这是因为现有的工作侧重于改进抽象下的算法，使用的分析方法并不总是能很好地反映实际场景。我的研究计划的最终目标是建模和预测一个“好的”在线算法在实践中的期望特征。为了实现这一目标，我的HQP和我将考虑三个具体方向。第一个方向是在为特定应用量身定制的现实模型下研究在线算法。我们设计和研究抽象的算法，它捕捉应用程序的本质，同时包括对性能有影响的细节。第二个方向涉及在应用程序允许的范围内放宽在线限制：有时可能会收到一些关于输入的“建议”，有时算法可以“推迟”之前的一些决定。我们设计了实用的“半在线”算法，这些算法通过有限的建议或延迟能力得到增强。第三个方向是使用捕获在线算法的最坏情况和平均情况行为的分析技术来研究在线算法。我们考虑了最近提出的双客观分析等措施来研究传统的最坏情况措施在实践中无法捕捉在线算法的典型性能的问题。我的研究项目的结果和影响将是显著的。首先，它将推进在线算法分析的理论方法。我的HQP和我将继续发表顶级的会议和期刊论文。其次，我们将为现实世界的应用设计实用算法，如数据压缩、社交网络分区、多核缓存以及与云计算领域相关的应用。其目的不仅是为这些应用程序设计良好的算法，而且在此过程中创造新的工具和方法来分析广泛的在线问题。这与我的项目的长期目标有关：结合分析和计算技术来描述实用的在线算法和设计这种算法的一系列理论工具。最后，该项目将直接培养博士2名，硕士6名，本科生7名。这些学生将发展在线计算领域的关键技能，使他们能够继续在该领域进行研究，并将他们的知识转化为在其产品和服务中使用在线算法的行业。