Research Article
The Subset-Sum Problem: Revisited with an Improved Approximated Solution
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 114 - Issue 14 |
| Published: March 2015 |
| Authors: Hashem A. Isa, Saleh Oqeili, Sulieman Bani-Ahmad |
10.5120/20043-7214
|
Hashem A. Isa, Saleh Oqeili, Sulieman Bani-Ahmad . The Subset-Sum Problem: Revisited with an Improved Approximated Solution. International Journal of Computer Applications. 114, 14 (March 2015), 1-5. DOI=10.5120/20043-7214
@article{ 10.5120/20043-7214,
author = { Hashem A. Isa,Saleh Oqeili,Sulieman Bani-Ahmad },
title = { 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 },
doi = { 10.5120/20043-7214 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2015
%A Hashem A. Isa
%A Saleh Oqeili
%A Sulieman Bani-Ahmad
%T The Subset-Sum Problem: Revisited with an Improved Approximated Solution%T
%J International Journal of Computer Applications
%V 114
%N 14
%P 1-5
%R 10.5120/20043-7214
%I Foundation of Computer Science (FCS), NY, USA
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.
Index Terms
Keywords