9338

Автор(ы): 

Автор(ов): 

3

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

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

Книга (брошюра, монография, стандарт)

Название: 

A Modification of Dynamic Programming Algorithms to Reduce the Running Time or/and Complexity

Город: 

  • Magdeburg

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

  • Otto-von-Guericke Universitaet Magdeburg

Год издания: 

2010

Объём, стр.: 

24
Аннотация
In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For the knapsack problem and some single machine scheduling problems, it is shown that the time complexity of the GrA is less that the time complexity of the standard DPA. Moreover, the average running time of the GrA is often essentially smaller. A GrA can also solve largescale instances and instances, where the parameters are not integer. In addition, for some problems, GrA has a polynomial time complexity in contrast to a pseudo-polynomial complexity of DPA.

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

Гафаров Е.Р., Лазарев А.А., Werner F. A Modification of Dynamic Programming Algorithms to Reduce the Running Time or/and Complexity. Magdeburg: Otto-von-Guericke Universitaet Magdeburg, 2010. – 24 с.