Approximability of Two Variants of Multiple Knapsack Problems

DOI10.1007/978-3-319-18173-8_27zbMath1459.68232OpenAlexW2095673391MaRDI QIDQ2947034

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

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

Related Items

Online knapsack of unknown capacity. How to optimize energy consumption in smartphones

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An efficient approximation 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
• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• A \((1-1/e)\)-approximation algorithm for the generalized assignment problem
• Tight Approximation Algorithms for Maximum Separable Assignment Problems
• Linear degree extractors and the inapproximability of max clique and chromatic number