Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems
Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems
复制标题
组合优化问题的一类动态规划复杂度的指数下界
DOI：
10.1007/s00453-010-9475-0
复制
发表时间：
2012
期刊：
影响因子：
1.1
通讯作者：
A. Bompadre
中科院分区：
文献类型：
--
作者：
A. Bompadre
本文证明了一类组合优化问题的动态规划（DP）的运行时间的指数下界。类的DP，我们推导出的下限是一般的，足以包括著名的DP组合优化问题，如开发的最短路径问题，背包问题，或旅行推销员问题。分析的问题包括旅行商问题（TSP）、二分匹配问题（BMP）、最小割和最大割问题（MCP）、最小划分问题（MPP）和最小代价测试集问题（MCTCP），并将动态程序与多项式求值算法联系起来。然后，我们推导和使用多项式评估的复杂性结果证明类似的结果为TSP或BMP的动态程序。我们定义了一个减少之间的问题，使我们能够概括这些边界的问题，无论是TSP或BMP变换。此外，我们证明了一些标准的问题之间的转换是这种。以这种方式，我们扩展到其他组合优化问题的下限。
We prove exponential lower bounds on the running time of Dynamic Programs (DP) of a certain class for some Combinatorial Optimization Problems. The class of DPs for which we derive the lower bounds is general enough to include well-known DPs for Combinatorial Optimization Problems, such as the ones developed for the Shortest Path Problem, the Knapsack Problem, or the Traveling Salesman Problem. The problems analyzed include the Traveling Salesman Problem (TSP), the Bipartite Matching Problem (BMP), the Min and the Max Cut Problems (MCP), the Min Partition Problem (MPP), and the Min Cost Test Collection Problem (MCTCP).We draw a connection between Dynamic Programs and algorithms for polynomial evaluation. We then derive and use complexity results of polynomial evaluation to prove similar results for Dynamic Programs for the TSP or the BMP. We define a reduction between problems that allows us to generalize these bounds to problems for which either the TSP or the BMP transforms to. Moreover, we show that some standard transformations between problems are of this kind. In this fashion, we extend the lower bounds to other Combinatorial Optimization Problems.