Result: 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.