38686

Автор(ы): 

Автор(ов): 

4

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

A New Effective Dynamic Program for an Investment Optimization Problem

ISBN/ISSN: 

ISSN 0005-1179

DOI: 

10.1134/S0005117916090101

Наименование источника: 

  • Automation and Remote Control

Обозначение и номер тома: 

Vol. 77, No. 9

Город: 

  • Москва

Издательство: 

  • SP MAIK Nauka/Interperiodica

Год издания: 

2016

Страницы: 

1633–1648
Аннотация
After a series of publications of T.E. O’Neil et al. (e.g. in 2010), dynamic program- ming 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 previ- ously 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 in- vestment 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.

Библиографическая ссылка: 

Гафаров Е.Р., Долгий А.Б., Лазарев А.А., Werner F.?. A New Effective Dynamic Program for an Investment Optimization Problem // Automation and Remote Control. 2016. Vol. 77, No. 9. С. 1633–1648.

Публикация имеет версию на другом языке: 

Да

Связь с публикацией: