A Fast Heuristic Algorithm for Solving High-Density Subset-Sum Problems
Автор: Akash Nag
Журнал: International Journal of Mathematical Sciences and Computing(IJMSC) @ijmsc
Статья в выпуске: 2 vol.3, 2017 года.
Бесплатный доступ
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.
Subset-sum problem, NP-complete, heuristics, search, algorithms
Короткий адрес: https://sciup.org/15014265
IDR: 15014265
Список литературы A Fast Heuristic Algorithm for Solving High-Density Subset-Sum Problems
- 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.
- Ralph Merkle, and Martin E. Hellman. Hiding information and signatures in trapdoor knapsacks. Information Theory, IEEE Transactions. 24.5. pp:525-530. 1978.
- Adi Shamir. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. Advances in Cryptology. Springer, US. pp:279-288. 1983.
- E. F. Brickell. Solving low-density knapsacks. Advances in Cryptology, Proceedings of Crypto '83. Plenum Press, New York. pp:25-37. 1984.
- J. C. Lagarias, A. M. Odlyzko. Solving low-density subset sum problems. Journal of the ACM. 32(1). pp:229-246. 1985.
- S. Martello, and P. Toth. A new algorithm for the 0-1 knapsack problem. Management Science 34. pp:633-644. 1988.
- Matthijs J. Coster et al. Improved low-density subset sum algorithms. Computational complexity 2.2. pp:111-128. 1992.
- 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.
- 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.
- 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.
- 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.
- Martello, Silvano, and Paolo Toth. "Algorithms for knapsack problems." North-Holland Mathematics Studies 132 (1987): 213-257.
- 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.
- Kate, Aniket, and Ian Goldberg. "Generalizing cryptosystems based on the subset sum problem." International Journal of Information Security 10.3 (2011): 189-199.
- 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.
