An exact algorithm for the subset sum problem

An exact algorithm for the subset sum problem

0.00 Avg rating0 Votes
Article ID: iaor20022957
Country: Netherlands
Volume: 136
Issue: 1
Start Page Number: 57
End Page Number: 66
Publication Date: Jan 2002
Journal: European Journal of Operational Research
Authors: ,
Keywords: optimization, programming: dynamic
Abstract:

The subset sum problem (SSP) is defined as: ‘Given n positive integers w1,...,wn, 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−log2c2)c, clog2c}) 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.

Reviews

Required fields are marked *. Your email address will not be published.