An exact algorithm for the subset sum problem

DOI10.1016/S0377-2217(00)00329-5zbMath1087.90526MaRDI QIDQ5955091

Nei Yoshihiro Soma, Paolo Toth

Publication date: 2002

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

zbMATH Keywords

Dynamic programmingCombinatorial optimizationBinary treeCore problemSubset sum problem

Mathematics Subject Classification ID

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

Related Items (6)

An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem ⋮ An integrated cutting stock and sequencing problem ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ An improved balanced algorithm for the subset-sum problem ⋮ Parallel time and space upper-bounds for the subset-sum problem ⋮ Optimal parallel machines scheduling with availability constraints

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The bounded subset sum problem is almost everywhere randomly decidable in O(n)
• An algorithm for the solution of the 0-1 knapsack problem
• A polynomial approximation scheme for the subset sum problem
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• Fast Approximation Algorithms for Knapsack Problems
• Hard Knapsack Problems
• An Algorithm for Large Zero-One Knapsack Problems
• A Minimal Algorithm for the 0-1 Knapsack Problem

This page was built for publication: An exact algorithm for the subset sum problem