A fully polynomial approximation algorithm for the 0-1 knapsack problem

DOI10.1016/0377-2217(81)90175-2zbMath0473.90056OpenAlexW2067500652MaRDI QIDQ1159134

Osman Oguz, Michael J. Magazine

Publication date: 1981

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(81)90175-2

zbMATH Keywords

0-1 knapsack problempolynomial epsilon-approximation algorithmNP- complete problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Dynamic programming (90C39) Boolean programming (90C09)

Related Items

Multistage knapsack, An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, An FPTAS for the parametric knapsack problem, A new fully polynomial time approximation scheme for the interval subset sum problem, A faster FPTAS for the unbounded knapsack problem, Computing knapsack solutions with cardinality robustness, Approximability of Two Variants of Multiple Knapsack Problems, Learning-augmented algorithms for online subset sum, An efficient fully polynomial approximation scheme for the Subset-Sum problem., Approximate strong separation with application in fractional graph coloring and preemptive scheduling., Approximation for knapsack problems with multiple constraints, The multidimensional 0-1 knapsack problem: an overview., Algorithms for the bounded set-up knapsack problem, An improved approximation scheme for variable-sized bin packing, Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search, Unnamed Item, An FPTAS for the knapsack problem with parametric weights, Approximation algorithms for knapsack problems with cardinality constraints, Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems, Data dependent worst case bound improving techniques in zero-one programming, An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem, The multidimensional 0-1 knapsack problem -- bounds and computational aspects

Cites Work

• Unnamed Item
• Unnamed Item
• An algorithm and efficient data structures for the binary knapsack problem
• An Efficient Algorithm for the 0-1 Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• An algorithm for the 0/1 Knapsack problem
• An Appraisal of Some Shortest-Path Algorithms