IIIT Hyderabad Publications 


Design and Evaluation of Alternate Enumeration Techniques for Subset Sum ProblemAuthors: Avni Verma,Kamalakar Karlapalem Journal: ACM Journal of Experimental Algorithmics Volume: 22 Volume Number: 1 Date: 20170530 Report no: IIIT/TR/2017/40 AbstractThe subset sum problem, also referred as SSP, is a NPHard computational problem. SSP has its applications in broad domains like cryptography, number theory, operation research and complexity theory. The most famous algorithm for solving SSP is Backtracking Algorithm which has exponential time complexity. Therefore, our goal is to design and develop better alternate enumeration techniques for faster generation of SSP solutions. Given the set of first n natural numbers which is denoted by X n and a target sum S, we propose various alternate enumeration techniques which find all the subsets of X n that add up to sum S. In this paper, we present the mathematics behind this exponential problem. We analyze the distribution of power set of X n and present formulas which show definite patterns and relations among these subsets. We introduce three major distributions for power set of X n : Sum Distribution, LengthSum Distribution and Element Distribution. These distributions are prepossessing procedures for various alternate enumeration techniques for solving SSP. We propose novel algorithms: Subset Generation using Sum Distribution, Subset Generation using LengthSum Distribution, Basic Bucket Algorithm, Maximum and Minimum Frequency Driven Bucket Algorithms and Local Search using Maximal and Minimal Subsets for enumerating SSP. We compare the performance of these approaches against the traditional backtracking algorithm. The efficiency and effectiveness of these algorithms are presented with the help of these experimental results. Furthermore, we studied the over solution set of subsets generated by various algorithms to get the complete solution for subset sum problem. Finally, we present a conjecture about upper bound on the number of subsets that has to be enumerated to get all solutions for Subset Sum Problem. Full article: pdf Centre for Data Engineering 

Copyright © 2009  IIIT Hyderabad. All Rights Reserved. 