A Graphical Approach for Solving NP-Hard Combinatorial Problems

2008. No. 15.

Лазарев А. А., Вернер Ф.

In this paper we consider a graphical realization of dynamic programming. The concept is discussed on the partition and knapsack problems. In contrast to dynamic programming, the new algorithm can also treat problems with non-integer data without necessary transformations of the corresponding problem. We compare the proposed method with existing algorithms for these problems on small-size instances of the partition problem with $n \le 10$ numbers. For almost all instances, the new algorithm considers on average substantially less "stages" than the dynamic programming algorithm.

Ключевые слова: оптимизация, optimization, модели, models, scheduling theory, теория расписаний, приближенные алгоритмы, approximation algorithms