|
Avtomatika i Telemekhanika, 2016, Issue 9, Pages 150–166
(Mi at14555)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Control in Social Economic Systems, Medicine, and Biology
A new effective dynamic program for an investment optimization problem
E. R. Gafarova, A. Dolguib, A. A. Lazarevcdae, F. Wernerf a Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia
b Ecole Nationale Supérieure des Mines, IRCCYN, UMR CNRS 6597, Nantes, France
c Lomonosov Moscow State University, Moscow, Russia
d Moscow Institute of Physiscs and Technology, Dolgoprudny, Russia
e International Laboratory of Decision Choice and Analysis, National Research University, Higher School of Economics, Moscow, Russia
f Fakultät für Mathematik, Otto-von-Guericke-Universitäat Magdeburg, Magdeburg, Germany
Abstract:
After a series of publications of T. E. O'Neil et al. (e.g. in 2010), dynamic programming seems to be the most promising way to solve knapsack problems. Some techniques are known to make dynamic programming algorithms (DPA) faster. One of them is the graphical method that deals with piecewise linear Bellman functions. For some problems, it was previously shown that the graphical algorithm has a smaller running time in comparison with the classical DPA and also some other advantages. In this paper, an exact graphical algorithm (GrA) and a fully polynomial-time approximation scheme based on it are presented for an investment optimization problem having the best known running time. The algorithms are based on new Bellman functional equations and a new way of implementing the GrA.
Citation:
E. R. Gafarov, A. Dolgui, A. A. Lazarev, F. Werner, “A new effective dynamic program for an investment optimization problem”, Avtomat. i Telemekh., 2016, no. 9, 150–166; Autom. Remote Control, 77:9 (2016), 1633–1648
Linking options:
https://www.mathnet.ru/eng/at14555 https://www.mathnet.ru/eng/at/y2016/i9/p150
|
Statistics & downloads: |
Abstract page: | 344 | Full-text PDF : | 41 | References: | 42 | First page: | 32 |
|