IIIT Hyderabad Publications |
|||||||||
|
Design and Evaluation of Alternate Enumeration Techniques for Subset Sum ProblemAuthor: Avni Verma Date: 2017-07-31 Report no: IIIT/TH/2017/50 Advisor:Kamalakar Karlapalem AbstractThe subset sum problem, also referred to as SSP, is an NP-Hard computational problem. SSP has its applications in broad domains like cryptography, number theory, operations 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 thesis, 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, Length-Sum 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 Length-Sum 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 extra 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 thesis: pdf Centre for Data Engineering |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |