An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem

DOI10.1016/J.EJOR.2005.09.026MaRDI QIDQ852950zbMATH OpenOpenAlexFDO

Authors Carlos Alberto Alonso Sanches, Nei Yoshihiro Soma, Horacio Hideki Yanasse

Publication date 15 November 2006

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2005.09.026

zbMATH Keywords

parallel algorithmsKnapsack problemPRAM machinessubset-sum problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Parallel time and space upper-bounds for the subset-sum problem
• scientific article; zbMATH DE number 4035132
• Observations on optimal parallelizations of two-list algorithm
• Parallel approximation schemes for subset sum and knapsack problems
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method

Cites work

• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 774344 (Why is no real title available?)
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A Parallel Algorithm for the Knapsack Problem
• A parallel time/hardware tradeoff T.H=O(2/sup n/2/) for the knapsack problem
• A parallel two-list algorithm for the knapsack problem
• An exact algorithm for the subset sum problem
• Comments on parallel algorithms for the knapsack problem.
• Computing Partitions with Applications to the Knapsack Problem
• Discrete-variable extremum problems
• Fast and scalable parallel algorithms for knapsack-like problems.
• Parallel Merge Sort
• Parallel permutation and sorting algorithms and a new generalized connection network

Cited in

(9)

• Parallel time and space upper-bounds for the subset-sum problem
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
• A low-space algorithm for the subset-sum problem on GPU
• Parallel approximation schemes for subset sum and knapsack problems
• An improved balanced algorithm for the subset-sum problem
• A polynomial approximation scheme for the subset sum problem
• scientific article; zbMATH DE number 4035132 (Why is no real title available?)
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Observations on optimal parallelizations of two-list algorithm

This page was built for publication: An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem

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