08-15
A Graphical Approach for Solving NP-Hard Combinatorial Problems
Preprint series: 08-15, Preprints
The paper is published: Computers and Mathematics with Applications, Vol. 58, No. 4,
Abstract: 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 with at most 10 numbers in the partition problem. For almost all instances, the new algorithm considers on average substantially less stages than the dynamic programming algorithm.
Keywords: Dynamic programming, Exact algorithm, Graphical algorithm, Partition problem, Knapsack problem
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.