Parallel approximation schemes for subset sum and knapsack problems

DOI10.1007/BF00292111MaRDI QIDQ1084863zbMATH OpenFDO

Authors Joseph G. Peters, Larry Rudolph

Publication date 1987

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00292111

zbMATH Keywords

maximum numbers of processorsoptimization problemsparallel algorithmsparallel running times

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial optimization (90C27)

Review text

This paper presents parallel approximation schemes for the Subset Sum, 0- 1 Knapsack, and several other optimization problems. These algorithms offer a three-way trade-off among parallel time, the accuracy of the solution and the number of processors used. The maximum numbers of processors which can be usefully employed depend on n (the size of the input), and the accuracy requirement \(\epsilon\). The parallel running times of the algorithms are polynomial in both log n and log(1/\(\epsilon)\) when enough processors are used.

Recommendations

• Approximate algorithms for the Knapsack problem on parallel computers
• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• A Fast Approximation Algorithm For The Subset-Sum Problem
• scientific article; zbMATH DE number 4035132
• scientific article; zbMATH DE number 1104339

Cites work

• Algorithms for Scheduling Independent Tasks
• Combinatorial Problems: Reductibility and Approximation
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• General approximation algorithms for some arithmetical combinatorial problems
• scientific article; zbMATH DE number 3644795 (Why is no real title available?)
• scientific article; zbMATH DE number 3698707 (Why is no real title available?)
• scientific article; zbMATH DE number 3705908 (Why is no real title available?)
• scientific article; zbMATH DE number 3717131 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Parallel approximation schemes for subset sum and knapsack problems
• Parallelism in random access machines

Cited in

(10)

• Parallel approximation schemes for subset sum and knapsack problems
• Parallel approximation schemes for problems on planar graphs
• Hardness of approximation for knapsack problems
• Estimating the computational complexity of one variant of parallel realization of the branch-and-bound method for the knapsack problem
• scientific article; zbMATH DE number 4035132 (Why is no real title available?)
• A Fast Approximation Algorithm For The Subset-Sum Problem
• Approximate algorithms for the Knapsack problem on parallel computers
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• Parallel time and space upper-bounds for the subset-sum problem

This page was built for publication: Parallel approximation schemes for subset sum and knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1084863)