Approximation limits of dynamic programming

动态规划的近似极限

• 批准号: 389079104
• 负责人: Dr. Stasys Jukna
• 金额: --
• 依托单位: Lehrstuhl für Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2017
• 资助国家: 德国
• 起止时间: 2016-12-31 至 2020-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/389079104?language=en
• 关键词: Approximation; limits; dynamic; programming

Dynamic programming (DP) is a successful algorithmic paradigm for the solution of optimization, counting and decision problems. The limits of exact dynamic programming algorithms are currently relatively well understood: we are able to prove lower bounds on the number of necessary operations. The state of knowledge about the approximation power of dynamic programming algorithms, however, remained rather frustrating: no non-trivial lower bounds for approximating DP algorithms were known. During the appropriation period, we have closed this knowledge gap: we have proved the first, even exponential lower bounds also for approximating DP algorithms. We have also shown that randomization cannot substantially speed up DP algorithms.Our lower bounds hold for so-called pure DP algorithms using the basic (min,+) or (max,+) operations in their recursion equations. It turned currently out, also thanks to one of our new results, that the subtraction operation can exponentially speed up DP algorithms. The goal of the continuation of the project is to understand the reason for this surprising power of subtraction in dynamic programming. We are going to achieve this by proving lower bounds for DP algorithms with subtraction.

动态规划（DP）是求解优化、计数和决策问题的一种成功的算法范式。精确动态规划算法的极限目前已经被很好地理解了：我们能够证明必要运算次数的下界。然而，关于动态规划算法的近似能力的知识状态仍然相当令人沮丧：没有已知的近似DP算法的非平凡下界。在拨款期间，我们已经关闭了这一知识差距：我们已经证明了第一个，甚至指数下界也近似DP算法。我们还表明，随机化不能大大加快DP算法。我们的下界适用于在递归方程中使用基本（min,+）或（max,+）运算的所谓纯DP算法。现在，也多亏了我们的一个新结果，减法运算可以成倍地加速DP算法。本项目后续部分的目标是理解动态规划中减法的惊人威力的原因。我们将通过用减法证明DP算法的下界来实现这一点。

项目成果

Sorting Can Exponentially Speed Up Pure Dynamic Programming

排序可以成倍地加速纯动态编程

• DOI: 10.1016/j.ipl.2020.105962
• 发表时间: 2020
• 期刊: Electron. Colloquium Comput. Complex.
• 作者: S. Jukna;H. Seiwert
• 通讯作者: H. Seiwert

Approximation Limitations of Pure Dynamic Programming

纯动态规划的近似局限性

• DOI: 10.1137/18m1196339
• 发表时间: 2020
• 期刊: SIAM J. Comput.
• 作者: S. Jukna;H. Seiwert
• 通讯作者: H. Seiwert

Incremental versus Non-Incremental Dynamic Programming

• DOI: 10.1016/j.orl.2018.02.003
• 发表时间: 2018-05
• 期刊: Electron. Colloquium Comput. Complex.
• 作者: S. Jukna

Coin Flipping in Dynamic Programming Is Almost Useless

动态规划中的抛硬币几乎没有用

• DOI: 10.1145/3397476
• 发表时间: 2020
• 期刊: ACM Transactions on Computation Theory (TOCT)
• 作者: S. Jukna

Greedy can also beat pure dynamic programming

贪心也能打败纯动态规划

• DOI: 10.1016/j.ipl.2018.10.018
• 发表时间: 2019
• 期刊: Inf. Process. Lett.
• 作者: S. Jukna;H. Seiwert
• 通讯作者: H. Seiwert