A new effective dynamic program for an investment optimization problem

What is it about?

This paper gives an exact algorithm and a fully polynomial time approximation scheme for an investment optimization problem of selecting projects such that the total profit is maximized. The problem is a generaization of the knapsack problem. The algorithm improves the complexity of an algorithm given earlier by the authors in Journal of Mathematical Modelling and Algorithms in Operations Research (Vol. 13, No. 4, 2014, 597 - 614).

Featured Image

Why is it important?

The graphical method described in the paper is a general approach to improve dynamic programming algorithms. It can be applied to a great variety of problems.