Zurück zu den Preprints des Jahres 2008


A Graphical Approach for Solving NP-Hard Combinatorial Problems

by Lazarev, A., Werner, F..

Series: 2008-15, Preprints

90C39 Dynamic programming
90C27 Combinatorial optimization

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.

Dynamic programming, Exact algorithm, Graphical algorithm, Partition problem, Knapsack problem

This paper was published in:
Computers and Mathematics wit