A PTAS for the multiple knapsack problem

TLDR

The Multiple Knapsack problem generalizes the single knapsack by assigning items with profits and sizes to multiple bins, and is a special case of the APX‑hard Generalized Assignment problem, for which the best known approximation is due to Shmoys and Tardos. The goal is to find a subset of items of maximum profit that can be feasibly packed into the bins. We reduce any MKP instance to one with distinct sizes and profits while preserving a PTAS, enabling the design of a polynomial‑time approximation scheme. We present a PTAS for MKP, showing it is the strongest non‑APX‑hard special case of GAP, and that slight generalizations become APX‑hard, thereby delineating the boundary where GAP instances become APX‑hard.

Abstract

The Multiple Knapsack problem (MKP) is a natural and well known generalization of the single knapsack problem and is defined as follows. We are given a set of items and bins (knapsacks) such that each item has a profit and a size , and each bin has a capacity . The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the Generalized Assignment problem (GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a -approximation for it is implicit in the work of Shmoys and Tardos [26], and thus far, this was also the best known approximation for MKP. The main result of this paper is a polynomial time approximation scheme for MKP. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a ptas-preserving reduction from an arbitrary instance of MKP to an instance with distinct sizes and profits.