Call for Paper - May 2015 Edition
IJCA solicits original research papers for the May 2015 Edition. Last date of manuscript submission is April 20, 2015. Read More
The Subset-Sum Problem: Revisited with an Improved Approximated Solution
International Journal of Computer Applications
© 2015 by IJCA Journal
Volume 114 - Number 14
Year of Publication: 2015
|
10.5120/20043-7214 |
Hashem A Isa, Saleh Oqeili and Sulieman Bani-ahmad. Article: The Subset-Sum Problem: Revisited with an Improved Approximated Solution. International Journal of Computer Applications 114(14):1-5, March 2015. Full text available. BibTeX
@article{key:article,
author = {Hashem A. Isa and Saleh Oqeili and Sulieman Bani-ahmad},
title = {Article: The Subset-Sum Problem: Revisited with an Improved Approximated Solution},
journal = {International Journal of Computer Applications},
year = {2015},
volume = {114},
number = {14},
pages = {1-5},
month = {March},
note = {Full text available}
}
Abstract
The Subset-sum Problem is one of the easiest to describe and understand NP-complete problems. Available algorithms that solve this problem exactly need an exponential time, thus finding a solution to this problem is not currently feasible. The current paper revisits the subset-sum problem and suggests a new approach to find an approximate solution to this problem. The proposed algorithm gives a reasonable solution with a polynomial time-complexity.
References
- Baase, S. and Gelder, A. V. (2000). Computer Algorithms. Addison Wesley Longman.
- Bazgan, C. , Santha, M. , and Tuza, Z. (1998). Efficient approximation algorithms for the subset-sum equality problem.
- Bentley, J. (1986). Programming Pearls, Addison-Wesley Reading.
- Blair, C. (1994). Notes on Cryptography. Business Administration Dept. , University of Illinois, http://www. math. sunysb. edu/~scott/blair/Blair_s_Cryptography_Notes. html
- Borwein, J. and Bailey, D. (2003) Mathematics by Experiment: Plausible Reasoning in the 21st Century, Natick, MA: A. K. Peters.
- Cook, S. A. (1971). The complexity of theorem proving procedures. Third Annual ACM Symposium on the Theory of Computing, ACM, New York.
- Cormen, T. H. , Leiserson, C. E. , Rivest, R. L. , and Stein, C. (2001). Introduction to Algorithms, 2nd Edition. MIT Press and McGraw-Hill, 2001.
- Coster, M. J. ; Joux, A. ; LaMacchia, B. A. ; Odlyzko, A. M. ; Schnorr, C. P. ; and Stern, J. (1992). Improved Low-Density Subset-sum Algorithms, Computing Complex. 2.
- Ferguson, H. R. P. and Bailey, D. H. (1992). A Polynomial Time, Numerically Stable Integer Relation Algorithm, RNR Technical Report RNR-91-032.
- Garey, M. and Johnson, D. (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness.
- Garey, M. , Johnson, D. , and Stockmeyer, L. (1974). Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on Theory of computing. .
- Hodges, A. (1970). Alan Turing: The Enigma, Simon and Schuster, New York.
- Impagliazzo R. and Naor M. , (1996). Efficient cryptographic schemes provably as secure as subset-sum, Department of Computer Science, University of California at San Diego, 1996.
- Lagarias, L. C. and Odlyzko, A. M. (1985) "Solving Low-Density Subset-sum Problems. " Journal of ACM 32.
- Karp, R. (1972). Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations.
- Martello, S. and Toth, P. (1984). Worst case analysis of greedy algorithms for the subset-sum problem. Mathematical Programming.
- Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley.