Approximation for multi-knapsack problem
The multi-knapsack problem is defined as follows: For given \(n\) items and \(k\) knapsacks, there is a weight \(w_j\) and a value \(v_j\) for item \(j\) \((1\leq j\leq n)\), and a weight constraint \(B_i\) for knapsack \(i\) \((1\leq i\leq k)\), where \(w_j\), \(v_j\), \(B_i>0\). The object is to maximize the total value of all items packed in knapsacks subject to the constraint that the total weight of all items in each of the knapsacks does not exceed its weight constraint. When \(k\) is a fixed positive integer, the problem is called the \(k\)-knapsack problem. Especially, the 1-knapsack problem is just the ordinary \(0/1\) knapsack problem and has an FPTAS. We proved that for every fixed \(k\geq 2\), \(k\)-knapsack has a PTAS and a pseudo-polynomial time algorithm, but has no FPTAS unless \(P=NP\). In this note, we prove that if \(P\neq NP\), the multi-knapsack problem has no polynomial-time approximation algorithm \(A\) with \(R_A\leq {6\over 5}\). This remains true even if all knapsacks have the same weight constraints and every item's weight is equal to its value, i.e. \(B_i=B\) \((1\leq i\leq k)\) and \(w_j=v_j\) \((1\leq j\leq n)\). According to this theorem, the multi-knapsack problem has no PTAS. Moreover, we give a polynomial-time approximation algorithm with performance ratio 2 for the multi-knapsack problem.
- A successive approximation algorithm for the multiple knapsack problem
- The complexity of the 0/1 multi-knapsack problem
- Approximation algorithms for the multiple knapsack problem with assignment restrictions
- A PTAS for the multiple subset sum problem with different knapsack capacities
- Approximation for knapsack problems with multiple constraints
- Approximation issues of fractional knapsack with penalties: a note
- Approximating the product knapsack problem
- Hardness of approximation for knapsack problems
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- A Note on Approximation Schemes for Multidimensional Knapsack Problems
- A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
- Packing groups of items into multiple knapsacks
- Packing groups of items into multiple knapsacks
- scientific article; zbMATH DE number 1830735 (Why is no real title available?)
- On the proximity of the optimal values of the multi-dimensional knapsack problem with and without the cardinality constraint
- A fully polynomial approximation scheme for a knapsack problem with a minimum filling constraint (extended abstract)
- Approximation algorithms for the weight-reducible knapsack problem
This page was built for publication: Approximation for multi-knapsack problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1814715)
