Title

Speeding-up dynamic programming

Abstract

Dynamic programming is a well-known algorithm design technique which can be applied to a broad class of problems for which the so-called "principle of optimality" holds.

The solution of any dynamic program is described through a recurrence relation, so that its solution involves solving the same problem on smaller instances, which may overlap among each other.

Instead of solving the recurrence directly, which would imply to solve the same subproblems many times, a "table" is defined, in which each entry is a sub-problem whose resolution depends on some sub-problems located in entries on the table with smaller coordinates.

A naive algorithm for solving a dynamic program involves scanning the entire matrix in a suitable order, evaluating every dependency of each sub-problem. This leads to a time complexity which is proportional to the size of the matrix times the mean number of dependencies. This is indeed optimal when no structural properties on the input data can be shown.

However, this is not the case in many applications, where the dependencies among subproblems reflects the structural properties of the problem at hand. In these cases, those properties might be exploited to "prune" redundant computation, leading to polynomial speed-ups.

In this talk we expose some general techniques to achieve polynomial speed-ups when some specific properties on the dynamic programming formulations hold. We also illustrate a new general technique which has been used to speed-up the computation of a data compression problem, a result which suggest a promising research direction in this topic.