Power and Limitations of Conceptually Simple Algorithms

概念简单算法的威力和局限性

• 批准号: RGPIN-2019-06971
• 负责人: Pankratov, Denis
• 金额: $ 2.4万
• 依托单位: Concordia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=715673
• 关键词: Power; Limitations; Conceptually; Simple; Algorithms

Theoretical computer science has been hugely successful in terms of both design of new efficient and practical algorithms, as well as analysis and explanation of performance of existing algorithms. Yet, the gap between "theory" and "practice" remains. One of the most common criticisms is that worst-case analysis is often too pessimistic to reflect "practice". Prime examples of this phenomenon are linear programming and satisfiability problems. Another criticism is that negative results are often based on assumptions. Sometimes these assumptions are quite reasonable, such as P not equal to NP, but other times these assumptions are more controversial, such as strong exponential time hypothesis. Yet another criticism is that computational models might lack some practical features, e.g., extra side information that might be available to an algorithm. Side-information is often modelled in theory by an all-powerful oracle, where the "all-powerful" part is not very realistic. While there is no single "silver bullet" model that addresses all these concerns, there are many success stories in attempts to bridge practice and theory. This research program falls under this umbrella of trying to reduce the gap between theory and practice as it pertains to conceptually simple algorithms. Conceptually simple algorithms have many properties that make them desirable in practice, but they are hard to analyze. Part of the problem is that usually simple algorithms have bad worst-case behavior, but excellent empirical performance. An analysis consistent with such reality has to accurately model practical instances, which already is a very difficult task. Another problem is that the notion of simplicity is not well-defined. This makes negative answers to questions of the form "can this problem be solved by a simple algorithm?" impossible. The long-term goal of this project is to develop a formal theory of simple algorithms that would address the three criticisms mentioned above. Short-term goals consist of practical input modelling, algorithmic modelling with information-theoretic bottlenecks, and evaluation of conceptually simple algorithms for specific problems within various application domains, such as online advertising, scheduling, packing, and optimization.

理论计算机科学在设计新的有效和实用的算法以及分析和解释现有算法的性能方面都取得了巨大的成功。然而，“理论”与“实践”之间的差距依然存在。最常见的批评之一是，最坏情况分析往往过于悲观，无法反映“实践”。这种现象的主要例子是线性规划和可满足性问题。另一个批评是，负面结果往往是基于假设。有时这些假设是相当合理的，如P不等于NP，但其他时候这些假设是更有争议的，如强指数时间假设。另一个批评是，计算模型可能缺乏一些实用的功能，例如，可能对算法有用的额外辅助信息。边信息通常在理论上由全能的神谕建模，其中“全能”部分并不十分现实。虽然没有一个单一的“银弹”模式可以解决所有这些问题，但有许多成功的例子试图将实践和理论联系起来。这个研究计划属于这个试图减少理论和实践之间的差距，因为它涉及到概念上简单的算法的保护伞下福尔斯。概念上简单的算法有许多属性，使它们在实践中令人满意，但它们很难分析。问题的部分原因是，通常简单的算法具有糟糕的最坏情况行为，但具有出色的经验性能。符合这种现实的分析必须准确地模拟实际情况，这已经是一项非常困难的任务。另一个问题是简单性的概念没有很好的定义。这使得否定的答案形式的问题“这个问题可以解决一个简单的算法？“不可能。该项目的长期目标是开发简单算法的正式理论，以解决上述三个批评。短期目标包括实际的输入建模，算法建模与信息理论的瓶颈，并在各种应用领域，如在线广告，调度，包装和优化的具体问题的概念上简单的算法的评估。