An exact algorithm for the subset sum problem

The subset sum problem (SSP) is defined as: “Given n positive integers w 1,…, w n , find a combination amongst them such that their sum is the closest to, but not exceeding, a positive integer c”. We suggest an exact algorithm by introducing a new type of Core Problem and also, by using an improved...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2002, Vol.136 (1), p.57-66
Main Authors: Soma, Nei Yoshihiro, Toth, Paolo
Format: Article
Language:English
Subjects:
Algorithms
Binary tree
Combinatorial optimization
Core problem
Dynamic programming
Operations research
Optimization
Subset sum problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The subset sum problem (SSP) is defined as: “Given n positive integers w 1,…, w n , find a combination amongst them such that their sum is the closest to, but not exceeding, a positive integer c”. We suggest an exact algorithm by introducing a new type of Core Problem and also, by using an improved version of Bellman's recursion. We show that the resulting algorithm is bounded in time and space resource utilizations, respectively, by O( Max{(n− log 2c 2)c, c log 2c}) and O(n+c) . In addition to the sharp memory requirement decrease in comparison with any dynamic programming-based algorithm, the search space, for a vast range of instances, is restricted only to feasible states.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(00)00329-5