Title :
An efficient parallel algorithm for solving the knapsack problem on the hypercube
Author :
Goldman, Alfredo ; Trystram, D.
Author_Institution :
Inst. de Mecanique de Grenoble, Domaine Univ., France
Abstract :
The authors present a new algorithm to solve the integral knapsack problem on the hypercube. The main idea is to use the fact that the precedence graph of the dynamic programming function of the knapsack problem is an irregular mesh. They propose a scheduling algorithm for irregular meshes on the hypercube. The efficiency of the algorithm is independent on the number of processors. They also present some improvements for the solution of the 0/1 knapsack problem on the hypercube
Keywords :
dynamic programming; graph theory; hypercube networks; parallel algorithms; processor scheduling; 0/1 knapsack problem solving; dynamic programming function; efficient parallel algorithm; hypercube; integral knapsack problem solving; irregular mesh; irregular meshes; precedence graph; scheduling algorithm; Approximation algorithms; Art; Concurrent computing; Dynamic programming; Dynamic scheduling; Hypercubes; Parallel algorithms; Processor scheduling; Scheduling algorithm; Systolic arrays;
Conference_Titel :
Parallel Processing Symposium, 1997. Proceedings., 11th International
Conference_Location :
Genva
Print_ISBN :
0-8186-7793-7
DOI :
10.1109/IPPS.1997.580964
