A low-space algorithm for the subset-sum problem on GPU

DOI10.1016/J.COR.2017.02.006MaRDI QIDQ1652299zbMATH OpenOpenAlexFDO

Authors V. V. Curtis, Carlos Alberto Alonso Sanches

Publication date 11 July 2018

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2017.02.006

zbMATH Keywords

parallel algorithmGPUsubset-sum problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Numerical algorithms for specific classes of architectures (65Y10)

Recommendations

• Space-efficient approximations for subset sum
• Efficient GPU-based implementations of simplex type algorithms
• An Improved Low-Density Subset Sum Algorithm
• Improved low-density subset sum algorithms
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• scientific article; zbMATH DE number 4035132

Cites work

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (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?)
• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• Computing Partitions with Applications to the Knapsack Problem
• Parallel time and space upper-bounds for the subset-sum problem
• Solving knapsack problems on GPU

Cited in

(4)

• Parallel time and space upper-bounds for the subset-sum problem
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Solving knapsack problems on GPU
• An improved balanced algorithm for the subset-sum problem

Describes a project that uses

Uses Software

• CUDA

This page was built for publication: A low-space algorithm for the subset-sum problem on GPU

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