### Fast approximation scheme for the multiple knapsack problem

In this talk 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 S of all items in A of maximum total profit that can be packed into B without exceeding the capacities of the bins. Kellerer gave a polynomial time approximation scheme (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 efficient polynomial time approximation scheme (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).