The two list algorithm for the knapsack problem on an FPS T20
type: Item
instance of: scholarly article
title: The two list algorithm for the knapsack problem on an FPS T20
zbMATH Open document ID: 0669.65051
DOI: 10.1016/0167-8191(89)90121-X
published in: Parallel Computing
publication date: 1989-01-01T00:00:00Z
review text: The paper deals with a parallel implementation of the traditional two- list algorithm for the knapsack problem: given positive integers \(w_ 1,w_ 2,...,w_ n\) and M, find a subset L of \(\{\) 1,2,...,n\(\}\) such that \(w_ i=M\) where i's range over L. The current attempt aims at parallelizing by dividing the solution domain. Suppose there are \(2^ q\) processors labelled \(0,1,...,2^ q-1\) such that label j has \(R_ j\) as binary representation. A processor j works with \(W=(w_{q+1},...,w_ n)\) and \(M=M-\sum r_ kw_ r,\) \(1\leq k\leq i\). If a solution \(C_ j\) is found, then the final solution is the concatenation of \(R_ j\) and \(C_ j\). This parallelization yields a maximum speedup of \(2^{q/2}\). The algorithm was implemented on FPS T20 parallel machines (16 processors) coupled with hypercube topology, using OCCAM language.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 4096705
zbMATH Keywords: parallel computation
zbMATH Keywords: NP-complete
zbMATH Keywords: parallel algorithms
zbMATH Keywords: exponential complexity
zbMATH Keywords: Branch and bound algorithms
zbMATH Keywords: two-list algorithm
zbMATH Keywords: knapsack problem
zbMATH Keywords: hypercube
author: Michel Cosnard
author: Afonso G. Ferreira
author: Hugo Herbelin
reviewed by: N.A.Warsi
MaRDI profile type: Publication
full work available at URL: 0167-8191(89)90121-x
OpenAlex ID: W1976182275
description: scientific article; zbMATH DE number 4096705