Limitations of Incremental Dynamic Programming
Limitations of Incremental Dynamic Programming
复制标题
增量动态规划的局限性
DOI：
10.1007/s00453-013-9747-6
复制
发表时间：
2013
期刊：
影响因子：
1.1
通讯作者：
S. Jukna
中科院分区：
文献类型：
--
作者：
S. Jukna
我们认为所谓的“增量”动态规划算法，并有兴趣在他们所产生的子问题的数量。背包问题的经典动态规划算法是增量式的，产生nK个子问题和nK2个子问题之间的关系（线），其中是项目数，K是背包容量。我们表明，这个问题的任何增量算法必须产生aboutnKsubproblems，和aboutnKlogKwires（子问题之间的关系）是必要的。这甚至适用于子集和问题。我们还给出了近似背包问题所需的子问题的数量上界和下界。最后，我们证明了最大二部匹配问题和旅行商问题需要指数数量的子问题。本文的目标是利用布尔电路复杂性的思想和结果证明动态规划的下界。
We consider so-called “incremental” dynamic programming algorithms, and are interested in the number of subproblems produced by them. The classical dynamic programming algorithm for the Knapsack problem is incremental, producesnKsubproblems andnK2relations (wires) between the subproblems, wherenis the number of items, andKis the knapsack capacity. We show that any incremental algorithm for this problem must produce aboutnKsubproblems, and that aboutnKlogKwires (relations between subproblems) are necessary. This holds even for the Subset-Sum problem. We also give upper and lower bounds on the number of subproblems needed to approximate the Knapsack problem. Finally, we show that the Maximum Bipartite Matching problem and the Traveling Salesman problem require exponential number of subproblems. The goal of this paper is to leverage ideas and results of boolean circuit complexity for proving lower bounds on dynamic programming.
登录
查看更多内容
两次读取少数位或非法读取都没有多大帮助
DOI：
10.1016/s0166-218x(98)00042-0
发表时间：
1998
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
S. Jukna;A. Razborov
通讯作者：
A. Razborov
具有内存限制的线性时间 RAM 的确定性与非确定性
DOI：
10.1006/jcss.2002.1821
发表时间：
2002
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
M. Ajtai
通讯作者：
M. Ajtai
DOI：
10.1145/636865.636867
发表时间：
2003
期刊：
J. ACM
影响因子：
--
作者：
P. Beame;M. Saks;Xiaodong Sun;Erik Vee
通讯作者：
Erik Vee
组合优化问题的一类动态规划复杂度的指数下界
影响因子：
1.1
作者：
A. Bompadre
通讯作者：
A. Bompadre
DOI：
10.1016/j.tcs.2009.09.033
发表时间：
2004
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
A. Borodin;J. Boyar;Kim S. Larsen;Nazanin Mirmohammadi
通讯作者：
Nazanin Mirmohammadi