Investigating models, applications, and limitations of online algorithms

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

• 批准号: RGPIN-2018-06687
• 负责人: Kamali, Shahin
• 金额: $ 2.04万
• 依托单位: University of Manitoba
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=712892
• 关键词: 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名本科生的培训。这些学生将发展在线计算领域的关键技能，使他们能够继续研究这一领域，并将他们的知识转化为在产品和服务中使用在线算法的行业。