article

Free access

Approximate Algorithms for the 0/1 Knapsack Problem

Author:

Sartaj SahniAuthors Info & Claims

Journal of the ACM (JACM), Volume 22, Issue 1

Pages 115 - 124

https://doi.org/10.1145/321864.321873

Published: 01 January 1975 Publication History

PDF eReader

References

[1]

{:{OROWITZ, E., AND SAtINI, S, Computing partitions with apphcations to the knapsack problem. J ACM 21, 2 (April 1974), 277-292

Crossref

Google Scholar

[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.

Google Scholar

[3]

JoHNsoN, D. Approximation algorithms for combinatorial problems. Proc. Fifth Annual ACM Symposium on Theory of Computing, April 1973, pp. 38-49.

Crossref

Google Scholar

[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

Google Scholar

[5]

KOLESAR, P.J. A branch and bound algorithm for the knapsack problem. Manage. Sc~. 18 (1967), 723-735

Google Scholar

[6]

NEMHAI~SER, G, ~L., AND GARFINKEL, 1~. Integer Programmzng. Wiley, New York, 1972.

Google Scholar

[7]

N~MHAVS~a, G. L., ~ND ULLmAN, Z. Discrete dynamic programming and capital allocation. Manage. Sc~. i5, 9 (May 1969), 494-505

Google Scholar

[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.

Google Scholar

[9]

SA~.NI, S On the knapsack and other computatmnally related problems Ph D dins., Cornell U., Ithaca. N Y. 1973.

Google Scholar

Cited By

View all

Cisternas-Caneo FCrawford BSoto RGiachetti GPaz ÁPeña Fritz A(2024)Chaotic Binarization Schemes for Solving Combinatorial Optimization Problems Using Continuous MetaheuristicsMathematics10.3390/math1202026212:2(262)Online publication date: 12-Jan-2024
https://doi.org/10.3390/math12020262
Kesarwani MHaritsa J(2024)Index Advisors on Quantum PlatformsProceedings of the VLDB Endowment10.14778/3681954.368202517:11(3615-3628)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682025
Tang YLi QYin LLi DZhang YWang CZhang XQiao LZhang ZLu K(2024)DELTA: Memory-Efficient Training via Dynamic Fine-Grained Recomputation and SwappingACM Transactions on Architecture and Code Optimization10.1145/368933821:4(1-25)Online publication date: 20-Aug-2024
https://dl.acm.org/doi/10.1145/3689338
Show More Cited By

Index Terms

Approximate Algorithms for the 0/1 Knapsack Problem
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization

Recommendations

Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem

The 0-1 quadratic knapsack problem consists of maximizing a quadratic objective function subject to a linear capacity constraint. To exactly solve large instances of this problem with a tree search algorithm (e.g., a branch and bound method), the ...
Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

<P>It is well-known that many instances of the 0-1 knapsack problem can be effectively solved to optimality also for very large values of n the number of binary variables, while other instances cannot be solved for n equal to only a few hundreds. We ...
Using a Mixed Integer Programming Tool for Solving the 0-1 Quadratic Knapsack Problem

In this paper we will consider the 0-1 quadratic knapsack problem (QKP). Our purpose is to show that using a linear reformulation of this problem and a standard mixed integer programming tool, it is possible to solve the QKP efficiently in terms of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 22, Issue 1

Jan. 1975

172 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321864

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1975

Published in JACM Volume 22, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

276
Total Citations
View Citations
6,200
Total Downloads

Downloads (Last 12 months)767
Downloads (Last 6 weeks)98

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cisternas-Caneo FCrawford BSoto RGiachetti GPaz ÁPeña Fritz A(2024)Chaotic Binarization Schemes for Solving Combinatorial Optimization Problems Using Continuous MetaheuristicsMathematics10.3390/math1202026212:2(262)Online publication date: 12-Jan-2024
https://doi.org/10.3390/math12020262
Kesarwani MHaritsa J(2024)Index Advisors on Quantum PlatformsProceedings of the VLDB Endowment10.14778/3681954.368202517:11(3615-3628)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682025
Tang YLi QYin LLi DZhang YWang CZhang XQiao LZhang ZLu K(2024)DELTA: Memory-Efficient Training via Dynamic Fine-Grained Recomputation and SwappingACM Transactions on Architecture and Code Optimization10.1145/368933821:4(1-25)Online publication date: 20-Aug-2024
https://dl.acm.org/doi/10.1145/3689338
Miao CZhong ZXiao YYang FZhang SJiang YBai ZLu CGeng JHe ZWang YZou XYang CSekar VYu MSeneviratne AVeitch D(2024)MegaTE: Extending WAN Traffic Engineering to Millions of Endpoints in Virtualized CloudProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672242(103-116)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672242
Jungnitz NKeszocze ODe V(2024)SAS - A Framework for Symmetry-based Approximate SynthesisProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3658495(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3658495
Chen LLian JMao YZhang GMohar BShinkar IO'Donnell R(2024)A Nearly Quadratic-Time FPTAS for KnapsackProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649730(283-294)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649730
Liu YTan Y(2024)Improved Discrete Fireworks Algorithm for Large Scale Knapsack Problem2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10612146(01-10)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10612146
Sun ZZhou ZFu F(2024)Optimizing code allocation for hybrid on-chip memory in IoT systemsIntegration10.1016/j.vlsi.2024.10219597(102195)Online publication date: Jul-2024
https://doi.org/10.1016/j.vlsi.2024.102195
Bossaerts PBowman EFattinger FHuang HLee MMurawski CSuthakar ATang SYadav N(2024)Resource allocation, computational complexity, and market designJournal of Behavioral and Experimental Finance10.1016/j.jbef.2024.100906(100906)Online publication date: Mar-2024
https://doi.org/10.1016/j.jbef.2024.100906
Shi BFu LCao ZZhu L(2024)A second-pricing based incentive-compatible mechanism for matching and pricing in ride-sharingExpert Systems with Applications10.1016/j.eswa.2024.123377248(123377)Online publication date: Aug-2024
https://doi.org/10.1016/j.eswa.2024.123377
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem

Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

Using a Mixed Integer Programming Tool for Solving the 0-1 Quadratic Knapsack Problem

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations