This paper considers two variants of Multiple Knapsack Problems. The first one is the Multiple Knapsack Problem with Assignment Restrictions and Capacity Constraints (MK-AR-CC). In the MK-AR-CC(k) (where k is a positive integer), a subset of knapsacks is associated with each item and the item can be packed into only those knapsacks (Assignment Restrictions). Furthermore, the size of each knapsack is at least k times the largest item assignable to the knapsack (Capacity Constraints). The MK-AR-CC(k) is NP-hard for any constant k. In this paper, we give a polynomial-time " 1 + 2 k+1 + " -approximation algorithm for the MK-AR-CC(k), and give a lower bound on the approximation ratio of our algorithm by showing an integrality gap of`1 + 1 k − ´f or the IP formulation we use in our algorithm, where is an arbitrary small positive constant. The second problem is the Splittable Multiple Knapsack Problem with Assignment Restrictions (S-MK-AR), in which the size of items may exceed the capacity of knapsacks and items can be split and packed into multiple knapsacks. We show that approximating the S-MK-AR with the ratio of n 1− is NP-hard even when all the items have the same profit, where n is the number of items and is an arbitrary positive constant.
The method used in MK-AR-CC REF cannot solve our problem.
Approximability of Two Variants of Multiple Knapsack Problems
CIAC
Mathematics Computer Science