IJEEDC Design for Solving the Subset Sum Problem by Timing the Greedy Approach

Journal Paper

Paper Title :Design for Solving the Subset Sum Problem by Timing the Greedy Approach

Author :Soham Kapur, Arivarasi A

Article Citation :Soham Kapur ,Arivarasi A , (2024 ) " Design for Solving the Subset Sum Problem by Timing the Greedy Approach " , International Journal of Electrical, Electronics and Data Communication (IJEEDC) , pp. 6-11, Volume-12,Issue-9

Abstract : This paper demonstrates the use of a timer along with greedy algorithm for solving the Subset Sum Problem. It is a well-studied problem proven to be NP-complete. Several methods have been developed to achieve pseudo-polynomial and fully polynomial time complexity for the solution of the same. Here, an enhanced method is considered for finding an exact solution of the Subset Sum Problem, if it exists, using the binary search algorithm. A sorted single dimensional array of distinct non-negative numbers is used as the State Space. The method uses greedy and backtracking concepts. The algorithm takes low time complexity if the solution exists, and much more when the solution does not exist if the target sum is large enough. Utilizing this disparity, a time limit is used to find the solution, so that it takes less time than other existing algorithms in worst case, both theoretically and practically. It can be faster than the dynamic programming approach by an order of 10^3 in some cases. The algorithm itself is also useful in different variations and applications of the Subset Sum Problem. Keywords - Polynomial Time, Subset Sum Problem, Greedy Algorithm, Backtracking

Type : Research paper

Published : Volume-12,Issue-9


	\|		PDF	\|	Viewed - 16	\|	Published on 2025-01-10

Mar. 2025
Submitted Papers	:	80
Accepted Papers	:	10
Rejected Papers	:	70
Acc. Perc	:	12%
Issue Published	:	143
Paper Published	:	1781
No. of Authors	:	4956

Published : Volume-12,Issue-9

JOURNAL SUPPORTED BY