The Dynamic Programming Algorithm (DPA) was developed
in the fifties. However, it is sometimes still used nowadays
in various fields because it can easily find the global
optimum in certain optimization problems. DPA has been
applied to problems of one, two or three dimensions. When
the dimension of the problem solved by DPA is equal to one
the complexity of the algorithm is polynomial but if the size
is greater than one, the complexity becomes NP complete.
In such cases a practical implementation of the algorithm is
possible only using some approximation. In this paper we
present a novel approximation of the two-dimensional Dynamic
Programming Algorithm (2D-DPA) with polynomial
complexity. We then describe a parallel implementation of
the algorithm on a recent Graphics Processing Unit (GPU).
