The generalized assignment problem (GAP) [1] is given by:
Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and for each item $i$ and bin $j$, we are given a size $s(i, j)$ and a profit $p(i, j)$.
Objective: Find a subset $U ⊆ S$ that has a feasible packing in $B$ and maximizes the profit of the packing.
In [1], the authors proved that GAP is NP-hard even when:
- $p(i,j) = 1$ for all items $i$ and bins $j$.
- $s(i,j)=1$ or $s(i,j)=1+δ$ for all items $i$ and bins $j$.
- $c(j)=3$ for all bins $j$.
Analyzing this instance, I can see that GAP is NP-hard when $p(i,j)=1$ for all items $i$ and bins $j$ and each bin can pack at most three balls. This observation raises the following question for me.
My question: Is GAP NP-hard when $p(i,j) = 1$ for all items $i$ and bins $j$ and each bin can pack at most two balls?
[1] A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem