Limits of dynamic programming

动态规划的局限性

• 批准号: 237501959
• 负责人: Professor Dr. Georg Schnitger
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2013
• 资助国家: 德国
• 起止时间: 2012-12-31 至 2016-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/237501959?language=en
• 关键词: Limits; dynamic; programming

Our current knowledge of the dynamic programming complexity (DP complexity) of algorithmic problems is very disappointing, since the all-pairs shortest path problem is one of only few nontrivial algorithmic problems whose DP complexity is reasonably understood. The DP complexity of other shortest path problems remains unresolved as well the alleged optimality of the many fundamental dynamic programming algorithms in computer science and bioinformatics. We encounter the same bleak situation when approximating with dynamic programming algorithms.Our goal is to formulate adequate models capturing the paradigm of dynamic programming, and to prove lower bounds for important optimization problems in these models. In particular, powerful methods from boolean circuitcomplexity and communication complexity are to be modified to work also fordynamic programming algorithms.

我们目前的知识动态规划的复杂性（DP复杂性）的算法问题是非常令人失望的，因为所有对最短路径问题是仅有的几个非平凡的算法问题，其DP复杂性是合理的理解。其他最短路径问题的DP复杂性以及计算机科学和生物信息学中许多基本动态规划算法的所谓最优性仍然没有得到解决。 我们遇到了同样的惨淡的情况时，近似与动态规划算法。我们的目标是制定适当的模型捕捉动态规划的范例，并证明这些模型中的重要优化问题的下界。特别是，从布尔电路复杂性和通信复杂性的强大的方法进行修改，也为动态规划算法。

项目成果

On the optimality of Bellman-Ford-Moore shortest path algorithm

• DOI: 10.1016/j.tcs.2016.03.014
• 发表时间: 2016-05-16
• 期刊: THEORETICAL COMPUTER SCIENCE
• 影响因子: 1.1
• 作者: Jukna, Stasys;Schnitger, Georg
• 通讯作者: Schnitger, Georg

Minkowski Complexity of Sets: An Easy Lower Bound

集合的闵可夫斯基复杂度：一个简单的下界

• DOI: 10.4169/amer.math.monthly.124.8.749
• 发表时间: 2017
• 期刊: The American Mathematical Monthly
• 作者: Stasys

Lower bounds for monotone counting circuits

单调计数电路的下界

• DOI: 10.1016/j.dam.2016.04.024
• 发表时间: 2016
• 期刊: Electron. Colloquium Comput. Complex.
• 作者: S. Jukna

Tropical Complexity, Sidon Sets, and Dynamic Programming

热带复杂性、Sidon 集和动态规划

• DOI: 10.1137/16m1064738
• 发表时间: 2016
• 期刊: SIAM J. Discret. Math.
• 作者: S. Jukna

Complexity of Linear Boolean Operators

线性布尔运算符的复杂性

• DOI: 10.1561/0400000063
• 发表时间: 2013
• 期刊: Found. Trends Theor. Comput. Sci.
• 作者: S. Jukna;I. Sergeev
• 通讯作者: I. Sergeev