Title :
A new parallel algorithm for the knapsack problem and its implementation on a hypercube
Author :
Lin, Jianhua ; Storer, James A.
Author_Institution :
Dept. of Comput. Sci., Brandeis Univ., Waltham, MA, USA
Abstract :
A new parallel algorithm is presented for the 0/1 knapsack problem. On a hypercube of n processors, the algorithm runs in time O(mc(log n)/n), where m is the number of objects and c is the knapsack size. The best previous known hypercube algorithm takes time O(mc /n+c log n+c2). The new algorithm has been implemented on the Connection Machine and experimental results show that it performs very well for a wide range of problem sizes
Keywords :
operations research; parallel algorithms; Connection Machine; hypercube; knapsack problem; parallel algorithm; Application software; Computer science; Concurrent computing; Costs; Dynamic programming; Hypercubes; Industrial control; Integer linear programming; Parallel algorithms; Polynomials;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1990. Proceedings., 3rd Symposium on the
Conference_Location :
College Park, MD
Print_ISBN :
0-8186-2053-6
DOI :
10.1109/FMPC.1990.89428
