New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Fast approximation scheme for the multiple knapsack problem

SpeakerKlaus Jansen

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).