A Fast Heuristic Algorithm for Solving High-Density Subset-Sum Problems

Full Text (PDF, 352KB), PP.55-61

Views: 0 Downloads: 0

Author(s)

Akash Nag 1

1. Dept. of Computer Science, The University of Burdwan, Rajbati, Burdwan 713104, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijmsc.2017.02.05

Received: 7 Jan. 2017 / Revised: 3 Feb. 2017 / Accepted: 4 Mar. 2017 / Published: 8 Apr. 2017

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.