论文标题
纯动态编程的近似限制
Approximation Limitations of Pure Dynamic Programming
论文作者
论文摘要
我们证明了第一个，甚至是超级多项式的下限，在热带（min，+）和（Max，+）电路的大小上近似给定优化问题。许多用于优化问题的经典动态编程（DP）算法是纯粹的，因为它们仅在其递归方程中使用基本的最小值，max， +操作。热带电路构成了此类算法的严格数学模型。我们对热带电路的下限的算法结果是，纯DP算法和贪婪算法的近似功能是无与伦比的。纯粹的DP算法几乎无法在近似中击败贪婪。这种结果的新事实是，匡威也保持了。
We prove the first, even super-polynomial, lower bounds on the size of tropical (min,+) and (max,+) circuits approximating given optimization problems. Many classical dynamic programming (DP) algorithms for optimization problems are pure in that they only use the basic min, max, + operations in their recursion equations. Tropical circuits constitute a rigorous mathematical model for this class of algorithms. An algorithmic consequence of our lower bounds for tropical circuits is that the approximation powers of pure DP algorithms and greedy algorithms are incomparable. That pure DP algorithms can hardly beat greedy in approximation, is long known. New in this consequence is that also the converse holds.
