Zurück zu den Preprints des Jahres 2008


2008-15

A Graphical Approach for Solving NP-Hard Combinatorial Problems

by Lazarev, A., Werner, F..


Series: 2008-15, Preprints

MSC:
90C39 Dynamic programming
90C27 Combinatorial optimization

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

This paper was published in:
Computers and Mathematics wit