Parameterized Approximation Scheme for the Multiple Knapsack Problem

The multiple knapsack problem (MKP) is a well-known generalization of the classical knapsack problem. We are given a set $A$ of $n$ items and set $B$ of $m$ bins (knapsacks) such that each item $a \in A$ has a size $size(a)$ and a profit value $profit(a)$, and each bin $b \in B$ has a capacity $c(b)$. The goal is to find a subset $U \subset A$ of maximum total profit such that $U$ can be packed into $B$ without exceeding the capacities. The decision version of MKP is strongly NP-complete, since it is a generalization of the classical knapsack and bin packing problem. Furthermore, MKP does not admit an FPTAS even if the number $m$ of bins is two. Kellerer gave a PTAS for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with general capacities with running time $n^{O(\log(1/\epsilon) / \epsilon^8)}$. In this paper we propose an EPTAS with parameterized running time $2^{O(\log(1/\epsilon)/\epsilon^5)} \cdot poly(n) + O(m)$ for MKP. This solves also an open question by Chekuri and Khanna