International Journal of Mathematical Sciences and Computing (IJMSC)
IJMSC Vol. 3, No. 2, 8 Apr. 2017
Cover page and Table of Contents: PDF (size: 352KB)
A Fast Heuristic Algorithm for Solving High-Density Subset-Sum Problems
Full Text (PDF, 352KB), PP.55-61
Views: 0 Downloads: 0
Author(s)
Index Terms
Subset-sum problem, NP-complete, heuristics, search, algorithms
Abstract
The subset sum problem is to decide whether for a given set of integers A and an integer S, a possible subset of A exists such that the sum of its elements is equal to S. The problem of determining whether such a subset exists is NP-complete; which is the basis for cryptosystems of knapsack type. In this paper a fast heuristic algorithm is proposed for solving subset sum problems in pseudo-polynomial time. Extensive computational evidence suggests that the algorithm almost always finds a solution to the problem when one exists. The runtime performance of the algorithm is also analyzed.
Cite This Paper
Akash Nag,"A Fast Heuristic Algorithm for Solving High-Density Subset-Sum Problems", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.3, No.2, pp.55-61, 2017.DOI: 10.5815/ijmsc.2017.02.05
Reference
[1]Michael R. Garey, and David S. Johnson. Computers and Intractability: A Guide to the theory of NP-Completeness. WH Freeman & Co., New York. pp:223. 1979.
[2]Ralph Merkle, and Martin E. Hellman. Hiding information and signatures in trapdoor knapsacks. Information Theory, IEEE Transactions. 24.5. pp:525-530. 1978.
[3]Adi Shamir. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. Advances in Cryptology. Springer, US. pp:279-288. 1983.
[4]E. F. Brickell. Solving low-density knapsacks. Advances in Cryptology, Proceedings of Crypto '83. Plenum Press, New York. pp:25-37. 1984.
[5]J. C. Lagarias, A. M. Odlyzko. Solving low-density subset sum problems. Journal of the ACM. 32(1). pp:229-246. 1985.
[6]S. Martello, and P. Toth. A new algorithm for the 0-1 knapsack problem. Management Science 34. pp:633-644. 1988.
[7]Matthijs J. Coster et al. Improved low-density subset sum algorithms. Computational complexity 2.2. pp:111-128. 1992.
[8]Mark Chaimovich, Gregory Freiman, and Zvi Galil. Solving dense subset-sum problems by using analytical number theory. Journal of Complexity 5.3. pp:271-282. 1989.
[9]Zvi Galil, and Oded Margalit. An almost linear-time algorithm for the dense subset-sum problem. SIAM Journal on Computing 20.6. pp:1157-1189. 1991.
[10]Abraham D. Flaxman, and Bartosz Przydatek. Solving medium-density subset sum problems in expected polynomial time. STACS 2005. Springer Berlin Heidelberg. pp:305-314. 2005.
[11]Daxing L., Shaohan M. (1994) Two notes on low-density subset sum algorithm. In: Du DZ., Zhang XS. (eds) Algorithms and Computation. ISAAC 1994. Lecture Notes in Computer Science, vol 834. Springer, Berlin, Heidelberg.
[12]Martello, Silvano, and Paolo Toth. "Algorithms for knapsack problems." North-Holland Mathematics Studies 132 (1987): 213-257.
[13]Sharma, Sonal, Prashant Sharma, and Ravi Shankar Dhakar. "RSA algorithm using modified subset sum cryptosystem." Computer and Communication Technology (ICCCT), 2011 2nd International Conference on. IEEE, 2011.
[14]Kate, Aniket, and Ian Goldberg. "Generalizing cryptosystems based on the subset sum problem." International Journal of Information Security 10.3 (2011): 189-199.
[15]Dwork C., Naor M. (1993) Pricing via Processing or Combatting Junk Mail. In: Brickell E.F. (eds) Advances in Cryptology — CRYPTO' 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg.