A Graphical Approach for Solving NP-Hard Combinatorial Problems

by Lazarev, A.; Werner, F.


Preprint series: 08-15, Preprints

The paper is published: Computers and Mathematics with Applications, Vol. 58, No. 4,

90C39 Dynamic programming, See also {49L20}
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

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner:

Sie können eine Nachricht versenden an: Webmaster