β Scribed by Alexander A. Lazarev; Frank Werner
No coin nor oath required. For personal study only.
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 β€ 10 numbers. For almost all instances, the new algorithm considers on average substantially less ''stages'' than the dynamic programming algorithm.
π SIMILAR VOLUMES
In this paper, we combine the new global optimization method proposed by Jiao [H. Jiao, A branch and bound algorithm for globally solving a class of nonconvex programming problems, Nonlinear Anal. 70 (2) (2008) 1113-1123] with a suitable deleting technique to propose a new accelerating global optimi