"Design, analysis and theory of algorithms"

《算法的设计、分析与理论》

• 批准号: 7631-2012
• 负责人: Borodin, Allan
• 金额: $ 5.39万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=544428
• 关键词: Design; analysis; theory; algorithms

Algorithm design and analysis has seen significant progress in the sophistication of the algorithms being developed as well as in the expanding set of application areas where recent algorithms have become essential. However, algorithm design still remains mainly an art. The goal of this research project is to make algorithm design somewhat more of a science than an art. Namely, we wish to help develop a theory of algorithms that would allow us to better understand the benefits and limitations of general algorithmic approaches as applied to various problem domains. This general project is admittedly both too vague and too ambitious. So in more pragmatic terms, I am studying the power and limitations of well known "conceptually simple meta algorithms" such as greedy algorithms, dynamic programming, primal dual/local ratio algorithms and local search algorithms. To do so, we propose precise models that capture particular instances of such algorithms in relation to a wide variety of problem domains. We proceed to both design and analyze algorithms within a particular framework and as well to establish impossibility results (e.g. inapproximination bounds) with respect to the model. This approach stands in contrast to the fundamental limitations one tries to establish vis a vis complexity bounds (e.g. what can and cannot be computed in polynomial time or logarithmic space). Rather we try to establish limitations independent of complexity issues but instead establish such limitations based on the restricted design of the algorithm. In particular, we prove results that hold whether or not P = NP.

算法设计和分析已经看到了显着的进步，在复杂的算法正在开发，以及在不断扩大的应用领域，最近的算法已经成为必不可少的。然而，算法设计仍然主要是一门艺术。这个研究项目的目标是使算法设计更像一门科学而不是艺术。也就是说，我们希望帮助开发一种算法理论，使我们能够更好地理解应用于各种问题领域的一般算法方法的优点和局限性。这一总体计划诚然过于模糊，也过于雄心勃勃。因此，在更务实的条款，我正在研究的权力和局限性，众所周知的“概念简单的Meta算法”，如贪婪算法，动态规划，原始对偶/本地比率算法和本地搜索算法。要做到这一点，我们提出了精确的模型，捕捉特定的实例，这些算法在各种各样的问题域。我们继续在一个特定的框架内设计和分析算法，以及建立不可能的结果（例如，近似边界）的模型。 这种方法与人们试图建立的维斯维斯复杂性界限的基本限制（例如，在多项式时间或对数空间中可以计算和不能计算的内容）形成鲜明对比。相反，我们试图建立独立的复杂性问题的限制，而是建立这种限制的基础上的算法的限制设计。特别是，我们证明的结果，是否P = NP。