Is GAP NP-hard with at most two balls per bins?

Question

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

Answer 1

You can reduce numerical 3-dimensional matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\{x_1,\ldots,x_k\},Y=\{y_1,\ldots,y_k\},Z=\{z_1,\ldots,z_k\}$, you can construct $k$ bins with capacities $b-x_1+M+M^2,\ldots,b-x_k+M+M^2$, and $2k$ balls with sizes $y_1+M,\ldots,y_k+M, z_1+M^2,\ldots,z_k+M^2$, where $M$ is a very large number. Now there is a valid solution to the N3DM instance if and only if you can pack all the $2k$ balls.