Approximate Algorithms for the 0/1 Knapsack Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Approximate Algorithms for the 0/1 Knapsack Problem

Full text

Pdf (643 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 1 (January 1975) table of contents

Pages: 115 - 124

Year of Publication: 1975

ISSN:0004-5411

Author

Sartaj Sahni

Department of Computer, Information and Control Sciences, University of Minnesota, 114 Main Engineering Building, Minneapolis, MN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 26, Downloads (12 Months): 218, Citation Count: 27

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321864.321873 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ellis Horowitz , Sartaj Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the ACM (JACM), v.21 n.2, p.277-292, April 1974 [doi>10.1145/321812.321823]
	2	{NOARG~Or,A, G P, AND KORS~, J F A reduction algorithm for zero-one single knapsack problems. Manage Sc~ 20, 4 (Dec. 1973), 460-463.
	3	David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
	4	KARP, R Reduclbfllty among combinatorial problems. In Complexity of Computer Computatwns, R E Miller and J. W. Thatcher, Eds, Plenum Press, N Y., 1972, pp 85-104
	5	KOLESAR, P.J. A branch and bound algorithm for the knapsack problem. Manage. Sc~. 18 (1967), 723-735
	6	NEMHAI~SER, G, ~L., AND GARFINKEL, 1~. Integer Programmzng. Wiley, New York, 1972.
	7	N~MHAVS~a, G. L., ~ND ULLmAN, Z. Discrete dynamic programming and capital allocation. Manage. Sc~. i5, 9 (May 1969), 494-505
	8	SA~NI, S Some related problems from network flows, game theory and integer programming. Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory, Oct 1972, pp 130-138.
	9	SA~.NI, S On the knapsack and other computatmnally related problems Ph D dins., Cornell U., Ithaca. N Y. 1973.

CITED BY 27

	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982
	Greg N. Frederickson, Approximation Algorithms for Some Postman Problems, Journal of the ACM (JACM), v.26 n.3, p.538-554, july 1979
	Andris A. Zoltners, A Direct Descent Binary Knapsack Algorithm, Journal of the ACM (JACM), v.25 n.2, p.304-311, April 1978
	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977
	Sartaj K. Sahni, Algorithms for Scheduling Independent Tasks, Journal of the ACM (JACM), v.23 n.1, p.116-127, Jan. 1976
	Sanjeev Khanna , Rajeev Motwani, Towards a syntactic characterization of PTAS, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.329-337, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976
	D. S. Hirschberg , C. K. Wong, A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables, Journal of the ACM (JACM), v.23 n.1, p.147-154, Jan. 1976
	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998
	Robert W. Scheifler, An analysis of inline substitution for a structured programming language, Communications of the ACM, v.20 n.9, p.647-654, Sept. 1977
	Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975
	Federico Angiolini , Francesco Menichelli , Alberto Ferrero , Luca Benini , Mauro Olivieri, A post-compiler approach to scratchpad mapping of code, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA
	Alfredo Goñi , Arantza Illarramendi , Eduardo Mena , José Miguel Blanco, An Optimal Cache for a Federated Database System, Journal of Intelligent Information Systems, v.9 n.2, p.125-155, Sept./Oct. 1997
	B. Holtkamp , P. Wagner, An algorithm for selection of migration candidates, ACM SIGMICRO Newsletter, v.15 n.4, p.140-146, Dec. 1984
	Reynald Dumont , Fabio Pellacini , James A. Ferwerda, Perceptually-driven decision theory for interactive realistic rendering, ACM Transactions on Graphics (TOG), v.22 n.2, p.152-181, April 2003
	Yourim Yoon , Yong-Hyuk Kim , Byung-Ro Moon, An evolutionary lagrangian method for the 0/1 multiple knapsack problem, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	Shahrooz Feizabadi , Binoy Ravindran , E. Douglas Jensen, MSA: a memory-aware utility accrual scheduling algorithm, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	A. Portilla-Figueras , S. Salcedo-Sanz , P. Garcia-Diaz , K. Hackbarth, A genetic algorithm for solving the first price sealed bid auction in communication networks, Proceedings of the 5th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications, p.1-6, February 15-17, 2006, Madrid, Spain
	Zoheir Ezziane, Solving the 0/1 knapsack problem using an adaptive genetic algorithm, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.16 n.1, p.23-30, January 2002
	Paat Rusmevichientong , David P. Williamson, An adaptive algorithm for selecting profitable keywords for search-based advertising services, Proceedings of the 7th ACM conference on Electronic commerce, p.260-269, June 11-15, 2006, Ann Arbor, Michigan, USA
	Ashutosh Sarkar , Pratap K. J. Mohapatra, Maximum utilization of vehicle capacity: A case of MRO items, Computers and Industrial Engineering, v.54 n.2, p.185-201, March, 2008
	Minos N. Garofalakis , Banu Özden , Abraham Silberschatz, Resource Scheduling in Enhanced Pay-Per-View Continuous Media Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.516-525, August 25-29, 1997
	Jair Jehuda , Amos Israeli, Automated Meta-Control for Adaptable Real-Time Software, Real-Time Systems, v.14 n.2, p.107-134, March 1, 1998
	Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest—A Framework for Fast Decision Tree Construction of Large Datasets, Data Mining and Knowledge Discovery, v.4 n.2-3, p.127-162, July 2000
	Deepak Venugopal , Guoning Hu, Efficient signature based malware detection on mobile devices, Mobile Information Systems, v.4 n.1, p.33-49, January 2008
	Dafna Shahaf , Eric Horvitz, Investigations of continual computation, Proceedings of the 21st international jont conference on Artifical intelligence, p.285-291, July 11-17, 2009, Pasadena, California, USA