CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

The Subset-Sum Problem: Revisited with an Improved Approximated Solution

by Hashem A. Isa, Saleh Oqeili, Sulieman Bani-ahmad
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 114 - Number 14
Year of Publication: 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 },
issue_date = { March 2015 },
volume = { 114 },
number = { 14 },
month = { March },
year = { 2015 },
issn = { 0975-8887 },
pages = { 1-5 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume114/number14/20043-7214/ },
doi = { 10.5120/20043-7214 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:52:44.600066+05:30
%A Hashem A. Isa
%A Saleh Oqeili
%A Sulieman Bani-ahmad
%T The Subset-Sum Problem: Revisited with an Improved Approximated Solution
%J International Journal of Computer Applications
%@ 0975-8887
%V 114
%N 14
%P 1-5
%D 2015
%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
  1. Baase, S. and Gelder, A. V. (2000). Computer Algorithms. Addison Wesley Longman.
  2. Bazgan, C. , Santha, M. , and Tuza, Z. (1998). Efficient approximation algorithms for the subset-sum equality problem.
  3. Bentley, J. (1986). Programming Pearls, Addison-Wesley Reading.
  4. Blair, C. (1994). Notes on Cryptography. Business Administration Dept. , University of Illinois, http://www. math. sunysb. edu/~scott/blair/Blair_s_Cryptography_Notes. html
  5. Borwein, J. and Bailey, D. (2003) Mathematics by Experiment: Plausible Reasoning in the 21st Century, Natick, MA: A. K. Peters.
  6. Cook, S. A. (1971). The complexity of theorem proving procedures. Third Annual ACM Symposium on the Theory of Computing, ACM, New York.
  7. Cormen, T. H. , Leiserson, C. E. , Rivest, R. L. , and Stein, C. (2001). Introduction to Algorithms, 2nd Edition. MIT Press and McGraw-Hill, 2001.
  8. 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.
  9. Ferguson, H. R. P. and Bailey, D. H. (1992). A Polynomial Time, Numerically Stable Integer Relation Algorithm, RNR Technical Report RNR-91-032.
  10. Garey, M. and Johnson, D. (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness.
  11. Garey, M. , Johnson, D. , and Stockmeyer, L. (1974). Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on Theory of computing. .
  12. Hodges, A. (1970). Alan Turing: The Enigma, Simon and Schuster, New York.
  13. 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.
  14. Lagarias, L. C. and Odlyzko, A. M. (1985) "Solving Low-Density Subset-sum Problems. " Journal of ACM 32.
  15. Karp, R. (1972). Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations.
  16. Martello, S. and Toth, P. (1984). Worst case analysis of greedy algorithms for the subset-sum problem. Mathematical Programming.
  17. Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley.
Index Terms

Computer Science
Information Sciences

Keywords

NP-complete problem the subset-sum problem

Powered by PhDFocusTM