A Survey Of Parallel Algorithms For One-Dimensional Integer Knapsack Problems

This article surveys several methods that can be used to solve integer knapsack problems on a variety of parallel computing architectures. Parallel algorithms designed for a variety of one-dimensional knapsack problems on both theoretical PRAM models of computation and existing parallel architecture...

Full description

Saved in:
Bibliographic Details
Published in:INFOR. Information systems and operational research 1994-08, Vol.32 (3), p.163-186
Main Authors: Gerasch, Thomas E., Wang, Pearl Y.
Format: Article
Language:English
Subjects:
Algorithms
Integer programming
Knapsack problem
Parallel processing
Studies
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This article surveys several methods that can be used to solve integer knapsack problems on a variety of parallel computing architectures. Parallel algorithms designed for a variety of one-dimensional knapsack problems on both theoretical PRAM models of computation and existing parallel architectures are examined. First, exact parallel algorithms for one-dimensional exact sum, unbounded, and 0/1 knapsack problems are reviewed. These algorithms were developed from sequential table-based approaches, dynamic programming formulations, and reduction to circuit-valued or prefix convolution problems. Next, greedy algorithms and approximation algorithms for the one-dimensional subset sum, subset product, and 0/1 knapsack problems are also discussed. Experimental results that have been reported in the literature are summarized throughout this report.
ISSN:0315-5986
1916-0615
DOI:10.1080/03155986.1994.11732247