Parallel time and space upper-bounds for the subset-sum problem

DOI10.1016/J.TCS.2008.06.051MaRDI QIDQ955010zbMATH OpenOpenAlexFDO

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

Publication date 18 November 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.06.051

zbMATH Keywords

dynamic programmingknapsack problemparallel algorithmssubset-sum problemupper-bound complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Dynamic programming (90C39) Parallel algorithms in computer science (68W10)

Recommendations

• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• scientific article; zbMATH DE number 4035132
• 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
• A low-space algorithm for the subset-sum problem on GPU

Cites work

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• o(log⁴ n) time parallel maximal matching algorithm using linear number of processors
• A randomized linear-work EREW PRAM algorithm to find a minimum spanning forest
• An efficient parallel algorithm for solving the knapsack problem on hypercubes
• An exact algorithm for the subset sum problem
• An introduction to parallelism in combinatorial optimization
• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• Computing Partitions with Applications to the Knapsack Problem
• Parallel Merge Sort

Cited in

(10)

• Applications of mathematics to maritime search
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
• Simultaneous (poly-time, log-space) lower bounds
• scientific article; zbMATH DE number 4035132 (Why is no real title available?)
• Space-time tradeoffs for subset sum: an improved worst case algorithm
• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• A low-space algorithm for the subset-sum problem on GPU
• scientific article; zbMATH DE number 3982516 (Why is no real title available?)
• An improved balanced algorithm for the subset-sum problem

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Parallel time and space upper-bounds for the subset-sum problem

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