Approximability of two variants of multiple knapsack problems

DOI10.1007/978-3-319-18173-8_27MaRDI QIDQ2947034zbMATH OpenOpenAlexFDO

Authors Shuichi Miyazaki, Naoyuki Morimoto, Yasuo Okabe

Publication date 21 September 2015

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

Full work available at URL http://hdl.handle.net/2433/226945

zbMATH Keywords

approximation algorithmsmultiple knapsack problemassignment restrictions

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Approximation for knapsack problems with multiple constraints
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• scientific article; zbMATH DE number 1445306
• Parameterized approximation scheme for the multiple knapsack problem

Cites work

• scientific article; zbMATH DE number 2011855 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• A new polynomial-time algorithm for linear programming
• An approximation algorithm for the generalized assignment problem
• An efficient approximation for the generalized assignment problem
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Tight approximation algorithms for maximum separable assignment problems

Cited in

(11)

• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• LP based heuristics for the multiple knapsack problem with assignment restrictions
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• Approximation algorithms for a two-phase knapsack problem
• A successive approximation algorithm for the multiple knapsack problem
• Online knapsack of unknown capacity. How to optimize energy consumption in smartphones
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Approximate \#knapsack computations to count semi-fair allocations
• A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
• A Fast Approximation Scheme for the Multiple Knapsack Problem
• Upper and lower bounding procedures for the multiple knapsack assignment problem

This page was built for publication: Approximability of two variants of multiple knapsack problems

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