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

DOI10.1007/S00224-002-1076-0MaRDI QIDQ699820zbMATH OpenOpenAlexFDO

Authors Yingjie Liu

Publication date 25 September 2002

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-002-1076-0

zbMATH Keywords

fast approximation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• A new fully polynomial time approximation scheme for the Knapsack problem
• scientific article; zbMATH DE number 1182767
• scientific article; zbMATH DE number 7122316
• A new approximation algorithm for the knapsack problem
• Approximate algorithms for the Knapsack problem on parallel computers

Cited in

(10)

• A new fully polynomial time approximation scheme for the Knapsack problem
• Approximation algorithms for fractional knapsack problems
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• A new approximate algorithm for the knapsack problem
• scientific article; zbMATH DE number 1182767 (Why is no real title available?)
• scientific article; zbMATH DE number 6861894 (Why is no real title available?)
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• A new approximation algorithm for the knapsack problem
• Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses

This page was built for publication: The fully polynomial approximation algorithm for the 0-1 knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q699820)