Approximability of Two Variants of Multiple Knapsack Problems
From MaRDI portal
Publication:2947034
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
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
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