Zurück zu den Preprints des Jahres 2013


2013-02

Solving an Investment Optimization Problem by an Improved Graphical Approach

by Gafarov, E.R., Dolgui, A., Lazarev, A.A., Werner, F..


Series: 2013-02, Preprints

MSC:
90C27 Combinatorial optimization
90C39 Dynamic programming
90C10 Integer programming
90B50 Management decision making, including multiple objectives

Abstract:
In this paper, a graphical algorithm (GrA) for an investment optimization problem is presented. This algorithm is based on the same Bellman equations as the best known dynamic programming algorithm (DPA) for the problem but the GrA has several advantages in comparison with the DPA. Based on this GrA, a fully polynomial-time approximation scheme is proposed having the best known running time.

Keywords:
Investment problem; Dynamic programming; Graphical algorithm, FPTAS