Approximation algorithms for the weight-reducible knapsack problem

DOI10.1007/978-3-319-06089-7_14MaRDI QIDQ5410644zbMATH OpenOpenAlexFDO

Authors Marc Goerigk, Yogish Sabharwal, Anita Schöbel, Sandeep Sen

Publication date 16 April 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-06089-7_14

zbMATH Keywords

approximation algorithmsknapsack problemimprovable optimization problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Constant-time approximation algorithms for the knapsack problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Approximation for multi-knapsack problem
• How to pack your items when you have to buy your knapsack
• Knapsack with variable weights satisfying linear constraints

Cited in

(6)

• Simple but efficient approaches for the collapsing knapsack problem
• Decomposition approaches for recoverable robust optimization problems
• A SHORT NOTE ON THE REDUCIBILITY OF THE COLLAPSING KNAPSACK PROBLEM
• The robust knapsack problem with queries
• Approximation algorithms for knapsack problems with cardinality constraints
• Linear Time Algorithms for Knapsack Problems with Bounded Weights

This page was built for publication: Approximation algorithms for the weight-reducible knapsack problem

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