A fast approximation scheme for the multiple knapsack problem

In this paper we propose an improved efficient approximation scheme for the multiple knapsack problem (MKP). Given a set $A$ of $n$ items and set $B$ of $m$ bins with possibly different capacities, the goal is to find a subset $A'/ \subseteq A$ of maximum total profit that can be packed into $B$ without exceeding the capacities of the bins. Kellerer gave a PTAS for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with arbitrary capacities with running time $n^{O(1/ \epsilon^8 \log(1/\epsilon))}$. Recently we found an EPTAS for MKP with running time $2^{O(1/\epsilon^5 \log(1/\epsilon))} poly(n)$. Here we present an improved EPTAS with running time $2^{O(1/\epsilon \log(1/\epsilon)^4)} poly(n)$. If the modified round-up property for bin packing with different sizes is true, the running time can be improved to $2^{O(1/\epsilon \log(1/\epsilon)^2)} poly(n)$.

Logo BII



Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.


Citation style:
Could not load citation form.