Techniques for solving subset sum problems within a given tolerance

Techniques for solving subset sum problems within a given tolerance

0.00 Avg rating0 Votes
Article ID: iaor20072110
Country: United Kingdom
Volume: 12
Issue: 4
Start Page Number: 437
End Page Number: 454
Publication Date: Jul 2005
Journal: International Transactions in Operational Research
Authors: ,
Keywords: programming: dynamic
Abstract:

The subset sum problem is a simple and fundamental NP-hard problem that is found in many real world applications. For the particular application motivating this paper (combination weighers) a solution is required to the subset sum problem that is within a small tolerance level, and can be computed quickly. We propose four techniques for solving this problem. The first two techniques are based on an efficient number partitioning algorithm. These techniques can solve small problems very efficiently when the solution uses approximately half the available items. The next technique is an enumeration technique that is capable of solving small problems very efficiently. The last technique is a modified enumeration technique that improves a good solution in a structured manner. These techniques were found to perform efficiently on large and small problems and can outperform other techniques currently proposed in the literature under certain conditions.

Reviews

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