Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

Full text

Pdf (386 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 4 (October 1975) table of contents

Pages: 463 - 468

Year of Publication: 1975

ISSN:0004-5411

Authors

Oscar H. Ibarra	Department of Computer, Information, and Control Sciences, 114 Main Engineering Building, University of Minnesota, Minneapolis, MN
Chul E. Kim	Department of Computer, Information, and Control Sciences, 114 Main Engineering Building, University of Minnesota, Minneapolis, MN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 44, Downloads (12 Months): 365, Citation Count: 77

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/321906.321909 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	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	2	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]
	3	INGARGIOLA, G. P , AND KORSH, J F. A reduction algorithm for zero-one single knapsack problems. Manag. Sc, 20 (1973), 460--463.
	4	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]
	5	KARP, R. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Mdler and J. W. Thatcher, Eds, Plenum Press, N. Y., 1972, pp 85-104
	6	KOLESXR, P. J A branch and bound algorithm for the knapsack problem Manag ScI lS (1967), 723-735
	7	NEMHAUSER, G L., AND GARFINKEL, R. Integer Programming Wiley, New York, 1972.
	8	NEMHAUSER, G. L., AND ULLMAN, Z Discrete dynamic programming and capital allocation Manag. 8ci 15 (1969), 494-505.
	9	SAHNI, S Some related problems from network flows, game theory, and integer programming Proc of the 13th Annual IEEE Symp on Switching and Automata Theory, 1972, pp 130--138
	10	Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]
	11	SAHNI, S., AND GONZALES, T. P-complete problems and approximate solutmns Comput. Sci Teeh. Rep. 74-5, U. of Minnesota, Minneapolis, Minn., 1974.

CITED BY 77

	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Sartaj K. Sahni, Algorithms for Scheduling Independent Tasks, Journal of the ACM (JACM), v.23 n.1, p.116-127, Jan. 1976
	Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998
	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977
	Greg N. Frederickson, Approximation Algorithms for Some Postman Problems, Journal of the ACM (JACM), v.26 n.3, p.538-554, july 1979
	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
	Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
	Gerhard J. Woeginger, When does a dynamic programming formulation guarantee the existence of an FPTAS?, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.820-829, January 17-19, 1999, Baltimore, Maryland, United States
	Shlomo Moran, On the complexity of designing optimal partial-match retrieval systems, ACM Transactions on Database Systems (TODS), v.8 n.4, p.543-551, Dec. 1983
	Tomas Feder , Rajeev Motwani , Rina Panigrahy , Chris Olston , Jennifer Widom, Computing the median with uncertainty, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.602-607, May 21-23, 2000, Portland, Oregon, United States
	M. R. Garey , D. S. Johnson, `` Strong '' NP-Completeness Results: Motivation, Examples, and Implications, Journal of the ACM (JACM), v.25 n.3, p.499-508, July 1978
	Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987
	Shmuel Winograd, Complexity Of Computations, Proceedings of the 1978 annual conference, p.138-141, December 04-06, 1978, Washington, D.C., United States
	Jianer Chen , Antonio Miranda, A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.418-427, May 01-04, 1999, Atlanta, Georgia, United States
	Eric Angel , Evripidis Bampis , Alexander Kononov, On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems, Theoretical Computer Science, v.306 n.1-3, p.319-338, 5 September 2003
	Matthias Galota , Christian Glaßer , Steffen Reith , Heribert Vollmer, A polynomial-time approximation scheme for base station positioning in UMTS networks, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.52-59, July 2001, Rome, Italy
	Ravindran Kannan, Polynomial-Time Aggregation of Integer Programming Problems, Journal of the ACM (JACM), v.30 n.1, p.133-145, Jan. 1983
	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
	Petra Schuurman , Gerhard J. Woeginger, Scheduling a pipelined operator graph, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.207-212, January 09-11, 2000, San Francisco, California, United States
	Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976
	Shahram Ghandeharizadeh , Douglas J. Ierardi, Management of disk space with REBATE, Proceedings of the third international conference on Information and knowledge management, p.304-311, November 29-December 02, 1994, Gaithersburg, Maryland, United States
	Robert D. Carr , Lisa K. Fleischer , Vitus J. Leung , Cynthia A. Phillips, Strengthening integrality gaps for capacitated network design and covering problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.106-115, January 09-11, 2000, San Francisco, California, United States
	Guangting Chen , Guoliang Xue, K-pair delay constrained minimum cost routing in undirected networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.230-231, January 07-09, 2001, Washington, D.C., United States
	Pasquale De Meo , Jameson Mbale , Giorgio Terracina , Domenico Ursino, XICOMASQ: an XML-based information content oriented multi-agent system for QoS management in telecommunications networks, Web Intelligence and Agent System, v.2 n.1, p.55-70, August 2004
	Viggo Kann, Polynomially bounded minimization problems that are hard to approximate, Nordic Journal of Computing, v.1 n.3, p.317-331, Fall 1994
	Milind Dawande , Subodha Kumar , Chelliah Sriskandarajah, Performance bounds of algorithms for scheduling advertisements on a web page, Journal of Scheduling, v.6 n.4, p.373-393, July/August 2003
	Shane Dye , Leen Stougie , Asgeir Tomasgard, Approximation algorithms and relaxations for a service provision problem on a telecommunication network, Discrete Applied Mathematics, v.129 n.1, p.63-81, 15 June 2003
	Guangting Chen , Guoliang Xue, A PTAS for weight constrained Steiner trees in series-parallel graphs, Theoretical Computer Science, v.304 n.1-3, p.237-247, 28 July 2003
	Peter Damaschke, Optimizing a mail-order with discount and shipping costs, Information Processing Letters, v.82 n.2, p.93-97, 30 April 2002
	Hans Kellerer , Renata Mansini , Ulrich Pferschy , Maria Grazia Speranza, An efficient fully polynomial approximation scheme for the Subset-Sum problem, Journal of Computer and System Sciences, v.66 n.2, p.349-370, March 2003
	Cristina Bazgan , Miklos Santha , Zsolt Tuza, Efficient approximation algorithms for the subset-sums equality problem, Journal of Computer and System Sciences, v.64 n.2, p.160-170, March 2002
	Jian-Jia Chen , Tei-Wei Kuo , Chia-Lin Yang, Profit-driven uniprocessor scheduling with energy and timing constraints, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	Klaus Jansen , Guochaun Zhang, On rectangle packing: maximizing benefits, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Georgii Gens , Evgenii Levner, Complexity of approximation algorithms for combinatorial problems: a survey, ACM SIGACT News, v.12 n.3, Fall 1980
	B. Holtkamp , P. Wagner, An algorithm for selection of migration candidates, ACM SIGMICRO Newsletter, v.15 n.4, p.140-146, Dec. 1984
	Anshul Kothari , David C. Parkes , Subhash Suri, Approximately-strategyproof and tractable multiunit auctions, Decision Support Systems, v.39 n.1, p.105-121, March 2005
	Sergei Vassilvitskii , Mihalis Yannakakis, Efficiently computing succinct trade-off curves, Theoretical Computer Science, v.348 n.2, p.334-356, 8 December 2005
	Monaldo Mastrolilli , Marcus Hutter, Hybrid rounding techniques for knapsack problems, Discrete Applied Mathematics, v.154 n.4, p.640-649, 15 March 2006
	E. C. Xavier , F. K. Miyazawa, Approximation schemes for knapsack problems with shelf divisions, Theoretical Computer Science, v.352 n.1, p.71-84, 7 March 2006
	Kan Hung Wan , Chris Loeser, An overlay network for replica placement within a P2P VoD network, International Journal of High Performance Computing and Networking, v.3 n.5/6, p.320-335, March 2005
	Florian Diedrich , Klaus Jansen, Improved approximation algorithms for scheduling with fixed jobs, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.675-684, January 04-06, 2009, New York, New York
	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
	Rene Beier , Artur Czumaj , Piotr Krysta , Berthold Vöcking, Computing equilibria for a service provider game with (Im)perfect information, ACM Transactions on Algorithms (TALG), v.2 n.4, p.679-706, October 2006
	Rajeev Kumar , Nilanjan Banerjee, Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem, Theoretical Computer Science, v.358 n.1, p.104-120, 31 July 2006
	Quincy Wu , Chin Lung Lu , Richard Chia-Tung Lee, The approximability of the weighted Hamiltonian path completion problem on a tree, Theoretical Computer Science, v.341 n.1, p.385-397, 5 September 2005
	Jianer Chen , Xiuzhen Huang , Iyad A. Kanj , Ge Xia, Polynomial time approximation schemes and parameterized complexity, Discrete Applied Mathematics, v.155 n.2, p.180-193, January, 2007
	Wieslaw Kubiak, Minimization of ordered, symmetric half-products, Discrete Applied Mathematics, v.146 n.3, p.287-300, 15 March 2005
	Guoliang Xue , Arunabha Sen , Weiyi Zhang , Jian Tang , Krishnaiya Thulasiraman, Finding a path subject to many additive QoS constraints, IEEE/ACM Transactions on Networking (TON), v.15 n.1, p.201-211, February 2007
	Christian Borgs , Jennifer Chayes , Nicole Immorlica , Kamal Jain , Omid Etesami , Mohammad Mahdian, Dynamics of bid optimization in online advertisement auctions, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Stavros G. Kolliopoulos , George Steiner, Partially ordered knapsack and applications to scheduling, Discrete Applied Mathematics, v.155 n.8, p.889-897, April, 2007
	Nir Halman , Diego Klabjan , Chung-Lun Li , James Orlin , David Simchi-Levi, Fully polynomial time approximation schemes for stochastic dynamic programs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.700-709, January 20-22, 2008, San Francisco, California
	Roee Engelberg , Jochen Könemann , Stefano Leonardi , Joseph (Seffi) Naor, Cut problems in graphs with a budget constraint, Journal of Discrete Algorithms, v.5 n.2, p.262-279, June, 2007
	Chris Olston , Jennifer Widom, Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data, Proceedings of the 26th International Conference on Very Large Data Bases, p.144-155, September 10-14, 2000
	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
	Mikhail Y. Kovalyov , Wieslaw Kubiak, A Fully Polynomial Approximation Scheme for Minimizing Makespan of Deteriorating Jobs, Journal of Heuristics, v.3 n.4, p.287-297, March 1998
	Mikhail Y. Kovalyov , Frank Werner, Approximation Schemes for Scheduling Jobs with Common Due Date on Parallel Machines to Minimize Total Tardiness, Journal of Heuristics, v.8 n.4, p.415-428, July 2002
	Zohar Naor, A collaborative wireless access to on-demand services, Advances in Multimedia, v.8 n.2, p.1-9, January 2008
	Guoliang Xue , Weiyi Zhang , Jian Tang , Krishnaiyan Thulasiraman, Polynomial time approximation algorithms for multi-constrained QoS routing, IEEE/ACM Transactions on Networking (TON), v.16 n.3, p.656-669, June 2008
	Rajeev Kumar , Ashwin H. Joshi , Krishna K. Banka , Peter I. Rockett, Evolution of hyperheuristics for the biobjective 0/1 knapsack problem by multiobjective genetic programming, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, Approximate and online multi-issue negotiation, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Hans Ulrich Simon, On the complexity of working set selection, Theoretical Computer Science, v.382 n.3, p.262-279, September, 2007
	Wolfgang Bein , José R. Correa , Xin Han, A fast asymptotic approximation scheme for bin packing with rejection, Theoretical Computer Science, v.393 n.1-3, p.14-22, March, 2008
	Kirk Pruhs , Gerhard J. Woeginger, Approximation schemes for a class of subset selection problems, Theoretical Computer Science, v.382 n.2, p.151-156, August, 2007
	Takehiro Ito , Erik D. Demaine , Xiao Zhou , Takao Nishizeki, Approximability of partitioning graphs with supply and demand, Journal of Discrete Algorithms, v.6 n.4, p.627-650, December, 2008
	A. V. Eremeev , M. Ya. Kovalyov , P. M. Kuznetsov, Approximate solution of the control problem of supplies with many intervals and concave cost functions, Automation and Remote Control, v.69 n.7, p.1181-1187, July 2008
	Erdal Erel , Jay B. Ghosh, Note: FPTAS for half-products minimization with scheduling applications, Discrete Applied Mathematics, v.156 n.15, p.3046-3056, August, 2008
	Chaitanya Mishra , Nick Koudas, Interactive query refinement, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Daniel Berend , Steven S. Skiena , Yochai Twitto, Combinatorial dominance guarantees for problems with infeasible solutions, ACM Transactions on Algorithms (TALG), v.5 n.1, p.1-29, November 2008
	Meinolf Sellmann, Approximated consistency for the automatic recording constraint, Computers and Operations Research, v.36 n.8, p.2341-2347, August, 2009
	Takehiro Ito , Xiao Zhou , Takao Nishizeki, Partitioning graphs of supply and demand, Discrete Applied Mathematics, v.157 n.12, p.2620-2633, June, 2009
	Alejandro López-Ortiz , Spyros Angelopoulos , Angèle M. Hamel, Optimal scheduling of contract algorithms for anytime problems, Proceedings of the 21st national conference on Artificial intelligence, p.874-879, July 16-20, 2006, Boston, Massachusetts
	Imed Kacem , A. Ridha Mahjoub, Short Communication: Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers and Industrial Engineering, v.56 n.4, p.1708-1712, May, 2009
	Yanni Sun , Jeremy Buhler, Designing Patterns and Profiles for Faster HMM Search, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.6 n.2, p.232-243, April 2009
	Peter Jonsson , Andrei Krokhin , Fredrik Kuivinen, Hard constraint satisfaction problems have hard gaps at location 1, Theoretical Computer Science, v.410 n.38-40, p.3856-3874, September, 2009
	Marek Cygan , Łukasz Kowalik , Mateusz Wykurz, Exponential-time approximation of weighted set cover, Information Processing Letters, v.109 n.16, p.957-961, July, 2009