|
|||||
|
|
A new algorithm for the Integer Knapsack Problem and its parallelization |
|
| Authors: | F. Almeida F. García D. Morales J. Roda C. Rodríguez |
| Affiliation: | (1) Departamento de Estadística, Investigación Operativa y Computación, Universidad de La Laguna, La Laguna, Spain |
| Abstract: | Summary A new sequential algorithm with complexityO(M 2+n) for an Integer Knapsack Problem with capacityM andn objects is proposed. The correspondentO(M 2/p+n) parallel algorithm runs on a ring machine withp processors. Computational results on both a local area network and a transputer network are reported. |
| Keywords: | Dynamic Programming Integer Programming Knapsack Problem Parallel Computing Transputer Networks PVM |
| 本文献已被 SpringerLink 等数据库收录！ | |