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 in bins with possibly different capacities, the goal is to find a subset S subset of A of maximum total profit that can be packed into B without exceeding the capacities of the bins. 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 log(1/epsilon))) poly(n). Here we present an improved EPTAS with running time 2(O(1/epsilon log4(1/epsilon))) + poly(n). If the integrality gap between the ILP and LP objective values for bin packing with different sizes is bounded by a constant, the running time can be further improved to 2(O(1/epsilon log2 (1/epsilon))) + poly(n).