Parallel Algorithms for Knapsack Type Problems (Q4258595)

This book presents the design of parallel algorithms for a class of discrete optimization problems. The problems are knapsack type problems, which include the unbounded knapsack problem, the 0/1 knapsack problem, the subset sum problem, the change making problem and are chosen for many reasons: they are NP-hard, sufficiently simple and have a vast range of applications. Starting from the dynamic programming recurrence equations, the authors present the current research directions, including their substantial contribution, to the mapping of these equations onto regular arrays (systolic arrays) and MIMD distributed memory architectures. In the same time, the book concentrates on determining the probabilistic running time of knapsack problems. Chapter 1 is meant to make the reader familiar with topics as systolic arrays and MIMD distributed memory organization, knapsack problems and the dynamic programming approach; as a list of previous and new results is presented as well. In chapter 2, a heuristic technique for mapping KP (knapsack problems) recurrences onto systolic and non-modular linear arrays is described, including total time analysis. The third chapter, meant to study probabilistic bounds, presents modular systolic arrays for KP, where the number of cells depends on the weights of the problem. The mathematical expectation time, using both uniform and exponential distributions is investigated. The algorithms in chapter 2 and chapter 3 are simulated on a SIMD simulator using a Pascal like language. Chapter 4 considers designing 2D regular arrays for knapsack type problems. A more complex mapping of the recurrent equations is used. The mathematical expectation of the execution time is calculated and it proves to be optimal. Further improvements are also presented. Chapter 5 describes an implemetation of the dynamic programming method for KP on the distributed memory architecture. The topology chosen is a ring of processors. Data partitioning and data alllocation strategiesare analyzed; a parallel algorithm is proposed and it is shown that it leads to an improvement of some known algorithms. The PVM implementation is discussed, as well. Chapters 6 and 7 describe a systematic synthesis technique leading to a formal derivation of regular arrays for knapsack type problems. Chapter 6 presents the mapping of integral recurrences onto regular arrays. Timing and allocation functions for integral recurrences are described and parametric uniformization is discussed. The techniques are illustrated on KP and Recursive Doubling. Chapter 7 concerns mapping onto fixed sized arrays with lower dimensions. The systematic mapping of the KP onto such arrays is considered. It is shown how the KP can be uniformized to produce affine dependencies so that the normal procedure for deriving timing and allocation functions can be applied. The results prove to be better than some other known approaches. The last chapter contains a brief comparision between systematic and heuristic methods.