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

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?

• How much is $\delta$? Nov 7, 2019 at 2:32
• I think the authors wanted to say that the sizes are either $1$ or larger than $1$. I think it does not matter much about $\delta$, but probably $0<\delta<1$.
– Jika
Nov 7, 2019 at 3:01

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.

• Thanks. From N3DM to my problem that's fine. On the other hand, if we pack all $2k$ balls, how do we know that we solved N3DM? I mean maybe a bin packs more than two balls?
– Jika
Nov 8, 2019 at 14:30
• @Jika Didn't you say "each bin can pack at most two balls"? Nov 8, 2019 at 16:03
• @Jika Maybe I misunderstood your question, but it doesn't matter, this construction still works. If a bin packs more than two balls, it must pack more than two $y_i$ balls and zero $z_i$ balls, then another bin would pack more than one $z_i$ balls, which is impossible. Nov 8, 2019 at 16:18
• Yes, you are right. Each bin packs at most two balls, so my comment did not have much sense. So, if I pack $2k$ balls in my problem then each bin packs 2 balls and they must be one $y_i$ ball and one $z_i$ ball?
– Jika
Nov 8, 2019 at 16:37
• Yes, two $z_i$ balls are overweight and zero $z_i$ balls would make another bin overweight. Nov 8, 2019 at 16:41