An exact algorithm for the subset sum problem

DOI10.1016/S0377-2217(00)00329-5MaRDI QIDQ5955091zbMATH OpenFDO

Authors Nei Yoshihiro Soma, Paolo Toth

Publication date 2002

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

Full work available at URL https://doi.org/10.1016/S0377-2217(00)00329-5

zbMATH Keywords

Combinatorial optimizationDynamic programmingBinary treeSubset sum problemCore problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• A Fast Approximation Algorithm for the Subset-sum Problem
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A Fast Approximation Algorithm For The Subset-Sum Problem
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• The subset sum problem

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• scientific article; zbMATH DE number 1302173 (Why is no real title available?)
• A Minimal Algorithm for the 0-1 Knapsack Problem
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• A polynomial approximation scheme for the subset sum problem
• An Algorithm for Large Zero-One Knapsack Problems
• An algorithm for the solution of the 0-1 knapsack problem
• Fast Approximation Algorithms for Knapsack Problems
• Hard Knapsack Problems
• The bounded subset sum problem is almost everywhere randomly decidable in O(n)

Cited in

(12)

• Parallel time and space upper-bounds for the subset-sum problem
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• Optimal parallel machines scheduling with availability constraints
• Solutions for subset sum problems with special digraph constraints
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
• Dynamic programming for the subset sum problem
• AI*IA 2003: Advances in Artificial Intelligence
• An integrated cutting stock and sequencing problem
• Algebraic algorithms for variants of subset sum
• An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums
• An improved balanced algorithm for the subset-sum problem

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: An exact 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 Q5955091)