Approximation limits of 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.