An improved balanced algorithm for the subset-sum problem

DOI10.1016/J.EJOR.2018.11.055MaRDI QIDQ1713739zbMATH OpenOpenAlexWikidataFDO

Authors V. V. Curtis, Carlos Alberto Alonso Sanches

Publication date 28 January 2019

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

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

zbMATH Keywords

computing scienceNP-hard problemsubset-sum problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Integer programming (90C10) Combinatorial optimization (90C27)

Recommendations

• An exact algorithm for the subset sum problem
• Parallel time and space upper-bounds for the subset-sum problem
• A near-linear pseudopolynomial time algorithm for subset sum
• Effective parallelization strategy for the solution of subset sum problems by the branch-and-bound method
• Two linear approximation algorithms for the subset-sum problem

Cites work

• A faster pseudopolynomial time algorithm for subset sum
• A low-space algorithm for the subset-sum problem on GPU
• A near-linear pseudopolynomial time algorithm for subset sum
• An exact algorithm for the subset sum problem
• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• Computing Partitions with Applications to the Knapsack Problem
• Dynamic programming on the word RAM
• 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?)
• Improved low-density subset sum algorithms
• Parallel time and space upper-bounds for the subset-sum problem
• Solving low-density subset sum problems

Cited in

(2)

• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• On binary solutions to systems of equations

This page was built for publication: An improved balanced 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 Q1713739)